HDU - 1072 Nightmare
浏览数：27 /
时间：2015年06月09日
题意：求走出迷宫的最短时间，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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
