本文主要是介绍UVA 11624 搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出1000*1000矩阵，含起点‘J’，路‘.'，墙‘#’，火‘F'；
火每秒蔓延一格，人每秒走一步
问人是否可以安全走出矩阵，不能被火碰到
先对所有火BFS一遍，记录每个点被烧到的时间
然后对人BFS一遍，若到每点前没被火烧即可走
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
char str[1100][1100];
int n,m;
int fire[1100][1100],used[1100][1100];
struct node
{int x,y,t;
};int judge_fire(int x,int y)
{if (x<0 || y<0 || x>=n || y>=m) return 0;if (used[x][y]==1) return 0;if (str[x][y]=='#') return 0;return 1;
}void bfs_fire()
{queue<node>q;node cur,next;int i,j;memset(fire,-1,sizeof(fire));memset(used,0,sizeof(used));for (i=0;i<n;i++)for (j=0;j<m;j++)if (str[i][j]=='F'){cur.x=i;cur.y=j;cur.t=0;q.push(cur);used[i][j]=1;fire[i][j]=0;}while (!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (judge_fire(next.x,next.y)==0) continue;next.t=cur.t+1;used[next.x][next.y]=1;fire[next.x][next.y]=next.t;q.push(next);}}
}int judge_people(node b)
{if (str[b.x][b.y]=='#') return 0;if (used[b.x][b.y]==1) return 0;if (b.t>=fire[b.x][b.y] && fire[b.x][b.y]!=-1) return 0;return 1;
}int bfs_people()
{queue<node>q;node cur,next;int i,j;memset(used,0,sizeof(used));for (i=0;i<n;i++){for (j=0;j<m;j++)if(str[i][j]=='J'){cur.x=i;cur.y=j;cur.t=0;q.push(cur);used[i][j]=1;break;}if (j!=m) break;}while (!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];next.t=cur.t+1;if (next.x<0 || next.y<0 || next.x>=n || next.y>=m) return next.t;if (judge_people(next)==0) continue;q.push(next);used[next.x][next.y]=1;}}return -1;
}
int main()
{int Case,i,ans;scanf("%d",&Case);while (Case--){scanf("%d%d",&n,&m);for (i=0;i<n;i++)scanf("%s",str[i]);bfs_fire();ans=bfs_people();if (ans==-1)printf("IMPOSSIBLE\n");elseprintf("%d\n",ans);}return 0;
}
这篇关于UVA 11624 搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
