UVA 11624 Fire! 【特殊BFS】
题目链接
题意
人被困在迷宫里，有一些火苗在迷宫中会随时间蔓延，问人能否安全走到迷宫边界
分析
题本身很简单，只是这种题有两种处理方法：
- 火的状态很简单，只需要知道某个时间某个点有没有火，所以单独BFS一张火的图就可以了
- 一种比较巧妙的方法是，把火与人都当做BFS中的元素在一个队列中处理，注意BFS中同一层要先处理火，也就是最开始要先把火给入队
AC代码
（当时写的比较仓促，代码很丑……）
//UVA 11624 Fire!
//AC 2016-7-24 22:34:50
//BFS
#include
#include
//#define debugint G[1500][1500];
int R,C;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
vectorint ,int> > fires;int fx,fy;struct node
{int x,y;int steps;bool isfire;node(){}node(int a,int b,int c):x(a),y(b),steps(c),isfire(0){}bool operator< (const node &rhs) const{if(steps==rhs.steps)return !isfire;return steps>rhs.steps;}
}p,q;int visit[1500][1500];int BFS(int sx,int sy)
{if(sx==0||sx==R-1||sy==0||sy==C-1)return 1;inf(visit);priority_queue que;for(int i=0;i0);p.isfire=1;que.push(p);}que.push(node(sx,sy,0));while(que.size()){p=que.top();//cout<que.pop();if(p.isfire){if(G[p.x][p.y]continue ;elseG[p.x][p.y]=p.steps;for(int i=0;i<4;++i){q.x=p.x+dx[i];q.y=p.y+dy[i];q.steps=p.steps+1;q.isfire=1;if(q.x>=0&&q.x=0&&q.yq.steps){G[q.x][q.y]=q.steps;que.push(q);}}continue;}if(visit[p.x][p.y]continue;if(p.x==0||p.x==R-1||p.y==0||p.y==C-1)return p.steps+1;for(int i=0;i<4;++i){q.x=p.x+dx[i];q.y=p.y+dy[i];q.steps=p.steps+1;q.isfire=0;if(q.x>=0&&q.y>=0&&q.xreturn -1;
}int main()
{#ifdef debugfreopen("E:\\Documents\\code\\input.txt","r",stdin);freopen("E:\\Documents\\code\\output.txt","w",stdout);#endifint T=0;scanf("%d",&T);char c;while(T--){scanf("%d %d",&R,&C);getchar();inf(G);int sx,sy;fires.clear();for(int i=0;ifor(int j=0;jif(c=='#')G[i][j]=-1;else if(c=='F'){G[i][j]=1;fires.push_back(make_pair(i,j));}else{G[i][j]=INF;if(c=='J'){sx=i;sy=j;}}}getchar();}int res=BFS(sx,sy);if(res==-1)printf("IMPOSSIBLE\n");elseprintf("%d\n",res);}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！