uva11624 - Fire!
uva11624 - Fire!
火在蔓延，人在走。火会蔓延，不会熄灭，我们可以确定某个点着火的时间（广搜）。对于J来说，要是他走到某点的时间比火蔓延到该点的时间要短，那么他走到该点的时候，火还没蔓延过来，他就可以走到该点，否则，不能进入该点。
数据地图表示：
-1 该点是墙或已经走过，不能走
-2 该点是通道还没有走过，火还没蔓延过来，可以走
0-x 该点在第x秒时，火能蔓延到该点
处理过程：
（1）输入并初始化，初步处理地图数据
（2）广搜标记地图，确定火蔓延情况
（3）广搜逃亡路线。
#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;int n,m; //地图大小int sx,sy; //起始位置int map[1002][1002]; //地图存储。“-1”是不能走，“-2” 是能走，“0-x”是火蔓延过来的时间int dir[4][2]={1,0,0,1,-1,0,0,-1}; //四个方向struct node //搜索结构体{ int x; int y; int step;}s,e;queue<node> q; //搜索共用队列void initial() //地图，队列初始化{ int i,j; char x[1002]; //暂存数组 memset(map,-1,sizeof(map)); //全部初始化为0 while(!q.empty())q.pop(); //情况队列 cin>>n>>m; for(i=0;i<n;i++) //输入地图，并处理 { cin>>x; for(j=0;j<m;j++) { if(x[j]=='.')map[i][j]=-2; //此处可走 else if(x[j]=='F') //此处有火 { map[i][j]=0; s.x=i; s.y=j; s.step=0; q.push(s); } else if(x[j]=='J')sx=i,sy=j; //起点 } //由于最开始全部赋值为-1，都默认为不能走，所以，输入为“#”时，不用再处理 } while(!q.empty()) //广度优先搜索，确定火蔓延到每个点的时间【可能蔓延不到】 { s=q.front(); q.pop(); for(i=0;i<4;i++)//四个方向搜索 { e.x=s.x+dir[i][0]; e.y=s.y+dir[i][1]; e.step=s.step+1; if(e.x<0||e.x>=n||e.y<0||e.y>=m||map[e.x][e.y]!=-2)continue; //该点在地图外面或该点不可被蔓延，不处理该点 map[e.x][e.y]=e.step; //记录蔓延过来的时间 q.push(e); } }}int bfsescap() //逃亡广搜，能逃亡成功就返回时间，否则，返回-1{ s.x=sx; s.y=sy; s.step=1; map[sx][sx]=-1; q.push(s); //起点入队 while(!q.empty()) { s=q.front(); if(s.x==n-1||s.x==0||s.y==m-1||s.y==0) return s.step; //起点要判断，放这里更合适【这点的疏忽，让我郁闷了三天】逃亡成功 q.pop(); for(int i=0;i<4;i++) //四个方向搜索 { e.x=s.x+dir[i][0]; e.y=s.y+dir[i][1]; e.step=s.step+1; if(e.x<0||e.x>=n||e.y<0||e.y>=m||(map[e.x][e.y]!=-2&&map[e.x][e.y]<e.step))continue; //不可走，不处理 map[e.x][e.y]=-1; q.push(e); } } return -1; //所有能走的地方都走了，还是没有逃出去。逃亡失败}int main(){ int t; cin>>t; //案例测试数据组数 while(t--) { initial(); //输入，赋值处理等初始化 int ans=bfsescap(); //逃亡广搜 if(ans==-1)cout<<"IMPOSSIBLE"<<endl; //结果分析，所有能走的节点都走过了，还没有逃出迷宫 else cout<<ans<<endl; } return 0;}