巡逻的机器人（状态bfs）

/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击： 链接被删请百度： CSDN tt2767 ///////////////////////////////////////////////////////////////////////////////////////////////////////

题解： 建一个三维数组d[N][N][N] , 前两维是坐标，第三维是血条，它的意思就是当血条为hp时是否经过这点。用结构体记录步数，，判断状态输出即可。

;PI = acos(0.0) * 2.0;const int N = 30;const int dx[] = {0,1,0,-1};const int dy[] = {-1,0,1,0};int n,m,k;struct P{int x,y,hp,cnt; //hp是血条，每次过障碍-1 ，cnt为当前步数P(int x = 0 , int y = 0,int hp = 0,int cnt = 0): x(x),y(y),hp(ph),cnt(cnt){}};int d[N][N][N]; //第三维为同过此坐标时的ph值int G[N][N];int bfs();int main(){int Case;scanf(“%d”,&Case);memset(G,-1,sizeof(G)); //记得重置地图while(Case–){scanf(“%d%d%d”,&m,&n,&k); //k为血条最大值for(int i = 0 ; i <m ; i++){getchar(); //吸收‘\n’for(int j = 0 ; j < n ; j++)scanf(“%d”,&G[i][j]);}printf(“%d\n”,bfs());}return 0 ;}int bfs(){memset(d,0,sizeof(d));P s(0,0,k,0) , g(m-1,n-1,k,0);d[0][0][k] = 1;queue<P> q;q.push(s);while(!q.empty()){P p = q.front(); q.pop();if(p.x == g.x &&p.y == g.y) return p.cnt; //达到终点返回步数if(p.hp >= 0) //有血才能继续走{P tmp;for(int i = 0 ; i< 4 ; i++){tmp.x = p.x + dx[i];tmp.y = p.y + dy[i];tmp.hp = G[tmp.x][tmp.y] ? p.hp -1 : k ; //遇到0时恢复满血tmp.cnt = p.cnt + 1;if(0 <= tmp.x && tmp.x < m && 0<= tmp.y && tmp.y <= n && d[tmp.x][tmp.y][tmp.hp] == 0 && tmp.hp >=0){d[tmp.x][tmp.y][tmp.hp] = 1;q.push(tmp);}}}}if(q.empty()) return -1; //没有到达终点}

也站在未路让我牵挂的人。