题目描述：
小H在一个划分成了n*m个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小H不可以静止不动）， 但不能离开封锁线，否则就被打死了。 刚开始时他有满血6点，每移动一格他要消耗1点血量。一旦小H的 血量降到 0， 他将死去。 他可以沿路通过拾取鼠标（什么鬼。。。）来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去， 他也不能通过拾取鼠标补满 HP。 即使在家门口死去， 他也不能算完成任务回到家中。
地图上有 5 种格子：
数字 0： 障碍物。
数字 1： 空地， 小H可以自由行走。
数字 2： 小H出发点， 也是一片空地。
数字 3： 小H的家。
数字 4： 有鼠标在上面的空地。
小H能否安全回家？如果能， 最短需要多长时间呢？
输入：
第一行两个整数n,m， 表示地图的大小为n*m。
下面 n 行， 每行 m 个数字来描述地图。
输出：
一行， 若小H不能回家， 输出-1,否则输出他回家所需最短时间。
样例输入：
3 3
2 1 1
1 1 0
1 1 3
样例输出：
4
说明/提示：
1<=n,m<=9
程序代码：
#include<iostream> #include<cstdio> using namespace std; #define N 15 int sx,sy,ex,ey,m,n,flag,minn=99999999; int map[N][N],book[N][N]; int next1[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; void dfs(int step,int x,int y,int blood) { int tx,ty; if(blood==0) return ; if(step>=minn) return ; if(x==ex&&y==ey) { if(step<minn) minn=step; if(flag==0) flag=1; return ; } for(int i=0;i<=3;i++) { tx=x+next1[i][0]; ty=y+next1[i][1]; if(tx<1||tx>n||ty<1||ty>m||map[tx][ty]==0) continue; if(book[tx][ty]==0) { book[tx][ty]=1; if(map[tx][ty]==4&&blood>1) dfs(step+1,tx,ty,6); else dfs(step+1,tx,ty,blood-1); book[tx][ty]=0; } } return ; } int main() { int i,j; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%1d",&map[i][j]); if(map[i][j]==2) { sx=i; sy=j; } if(map[i][j]==3) { ex=i; ey=j; } } } book[sx][sy]=1; dfs(0,sx,sy,6); if(flag) printf("%d\n",minn); else printf("-1\n"); return 0; }
