题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1072
题目大意：给一个地图，从起点开始往终点走，6s后会爆炸，当遇到‘4‘时，爆炸倒计时会重置为6s。问最短能几步走出来，不能就输出-1。
关键思想：由于规模很小，简单BFS即可，因为有折返的情况，所以二维的vis数组是不够的，可以扩展到三维。或者及时return，因为time是在减少的，所以层数不会太深。另外走过4后再走4是没什么效果的。
代码如下：
#include <iostream>#include <algorithm>#include <queue>using namespace std;int MAP[10][10];int dir[4][2]={0,1,1,0,0,-1,-1,0};int T,N,M;int sx,sy;struct node{ ???int x,y; ???int step,time;};int BFS(){ ???queue<node>q; ???q.push({sx,sy,0,6}); ???node nw,nt; ???while(!q.empty()){ ???????nw=q.front(); ???????q.pop(); ???????if(MAP[nw.x][nw.y]==3){ ???????????return nw.step; ???????} ???????for(int i=0;i<4;i++){ ???????????nt.x=nw.x+dir[i][0],nt.y=nw.y+dir[i][1]; ???????????nt.step=nw.step+1,nt.time=nw.time-1; ???????????if(nt.x>=1&&nt.x<=N&&nt.y>=1&&nt.y<=M&&nt.time>0&&MAP[nt.x][nt.y]){ ???????????????if(MAP[nt.x][nt.y]==4)nt.time=6,MAP[nt.x][nt.y]=0; ???????????????q.push(nt); ???????????} ???????} ???} ???return -1;}int main(){ ???scanf("%d",&T); ???while(T--){ ???????scanf("%d%d",&N,&M); ????????for(int i=1;i<=N;i++){ ???????????for(int j=1;j<=M;j++){ ???????????????scanf("%d",&MAP[i][j]); ???????????????if(MAP[i][j]==2)sx=i,sy=j; ???????????} ???????} ???????printf("%d\n",BFS()); ???} ???????return 0;} HDU 1072 [Nightmare] BFS
原文地址：http://www.cnblogs.com/G-M-WuJieMatrix/p/7435600.html