题目链接 Nightmare
炸弹爆炸的限时是6s,一步减掉1s，在'4'方块上炸弹爆炸时间重置为6s
但是走到'4'和终点时的剩余时间必须大于0
最短路径：bfs
注意每点可以重复走过，必须剪枝，否则就停不下来了
如果第二次走过‘1’时，bomb的剩余时间比之前更短，那就不用走了，不值得
第二次走过'4'时，虽然bomb可以重置为6，但是step肯定变大了，所以也不用走
#include <iostream> #include <stdio.h> #include <memory.h> #include <queue> using namespace std; struct node { int x,y; int step; int bomb; }; int N,M; int sx,sy,ex,ey; int g[10][10]; bool vis[10][10]; int bomb[10][10]; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; bool check(int x,int y) { if(x<0||x>N-1||y<0||y>M-1)return false; if(g[x][y]==0)return false; return true; } int bfs() { memset(vis,0,sizeof(vis)); memset(bomb,0,sizeof(bomb)); queue<node>q; node cur,next; cur.x=sx; cur.y=sy; cur.step=0; cur.bomb=6; bomb[sx][sy]=6; vis[sx][sy]=true; q.push(cur); while(!q.empty()){ cur=q.front();q.pop(); //cout<<cur.x<<","<<cur.y<<":"<<endl; //if(g[cur.x][cur.y]==3&&cur.bomb)return cur.step; for(int i=0;i<4;i++){ next.x=cur.x+dx[i]; next.y=cur.y+dy[i]; if(check(next.x,next.y)){ next.bomb=cur.bomb-1; if(next.bomb>0){ next.step=cur.step+1; if(g[next.x][next.y]==1){ //cout<<next.x<<" "<<next.y<<" "<<next.step<<" "<<next.bomb<<endl; if(!vis[next.x][next.y]||(vis[next.x][next.y]&&next.bomb>bomb[next.x][next.y])){ vis[next.x][next.y]=true; bomb[next.x][next.y]=next.bomb; q.push(next); } } else if(g[next.x][next.y]==4){ if(!vis[next.x][next.y]){ vis[next.x][next.y]=true; next.bomb=6; bomb[next.x][next.y]=6; g[next.x][next.y]=1; q.push(next); } } else if(g[next.x][next.y]==3)return next.step; } } } } return -1; } int main() { //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%d%d",&N,&M); for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ scanf("%d",&g[i][j]); if(g[i][j]==2){sx=i;sy=j;g[i][j]=1;} else if(g[i][j]==3){ex=i;ey=j;} } } printf("%d\n",bfs()); } return 0; }
