HDU - 1072 Nightmare
题意:求走出迷宫的最短时间,2代表起点,3代表出口,每次经过4都可以将爆炸时间归0,要在爆炸时间内出去
思路:这里的BFS,vis[][]不再代表是否走过而是距离爆炸的时间,还有就是可以重复的经过一个点,所以我们再次走到这个点的时候,如果能有更长的爆炸时间就入队
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int MAXN = 20; struct node{ int x,y,t,step; }tmp; queue<node> q; int dx[] = {-1,1,0,0}; int dy[] = {0,0,-1,1}; int map[MAXN][MAXN],vis[MAXN][MAXN]; int n,m,x1,y1,ans; void bfs(){ while (!q.empty()){ tmp = q.front(); q.pop(); int x = tmp.x,y = tmp.y,t = tmp.t - 1,step = tmp.step + 1; if (tmp.t == 0) continue; else { if (map[x][y] == 3){ ans = tmp.step; return; } if (map[x][y] == 4) t = 5; } for (int i = 0; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && vis[nx][ny] < t && map[nx][ny] != 0){ vis[nx][ny] = t; tmp.x = nx,tmp.y = ny; tmp.t = t,tmp.step = step; q.push(tmp); } } } } int main(){ 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",&map[i][j]); vis[i][j] = 0; if (map[i][j] == 2) x1 = i,y1 = j; } while (!q.empty()) q.pop(); ans = -1,vis[x1][y1] = 6; tmp. x = x1,tmp.y = y1,tmp.t = 6,tmp.step = 0; q.push(tmp); bfs(); printf("%d\n",ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。