UVA 11624 Fire!（BFS）

题目地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_PRoblem&problem=2671

思路：预处理出火到每个格子的最短时间，BFS即可。

#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=1000+50;const int INF=0x3f3f3f3f;const int dx[]= {-1,1,0,0};const int dy[]= {0,0,-1,1};struct Node{    int x,y,t;    Node(int x=0,int y=0,int t=0):x(x),y(y),t(t) {}};int r,c;queue<Node> q;int vis[maxn][maxn];char st[maxn][maxn];int fire[maxn][maxn];int isIn(int x,int y){    return x>=0&&x<r&&y>=0&&y<c;}int isOut(int x,int y){    return x==0||y==0||x==r-1||y==c-1;}void prepare(){    while(!q.empty())    {        Node now=q.front();        q.pop();        for(int i=0; i<4; i++)        {            Node nt;            nt.x=now.x+dx[i];            nt.y=now.y+dy[i];            nt.t=now.t+1;            if(isIn(nt.x,nt.y)&&!vis[nt.x][nt.y]&&st[nt.x][nt.y]!='#')            {                vis[nt.x][nt.y]=1;                fire[nt.x][nt.y]=min(fire[nt.x][nt.y],nt.t);                q.push(nt);            }        }    }}void init(){    for(int i=0; i<r; i++)        for(int j=0; j<c; j++)            fire[i][j]=INF;    while(!q.empty()) q.pop();    memset(vis,0,sizeof(vis));}void solve(int x,int y){    int flag=0,ans;    Node tmp=(Node)    {        x,y,0    };    while(!q.empty()) q.pop();    memset(vis,0,sizeof(vis));    q.push(tmp),vis[x][y]=1;    while(!q.empty())    {        Node now=q.front();        q.pop();        if(isOut(now.x,now.y))        {            flag=1;            ans=now.t;            break;        }        for(int i=0; i<4; i++)        {            Node nt;            nt.x=now.x+dx[i];            nt.y=now.y+dy[i];            nt.t=now.t+1;            if(isIn(nt.x,nt.y)&&!vis[nt.x][nt.y]&&st[nt.x][nt.y]!='#'&&nt.t<fire[nt.x][nt.y])            {                vis[nt.x][nt.y]=1;                q.push(nt);            }        }    }    if(flag) printf("%d/n",ans+1);    else printf("IMPOSSIBLE/n");}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int stx,sty;        scanf("%d%d",&r,&c);        init();        for(int i=0; i<r; i++)        {            getchar();            scanf("%s",st[i]);            for(int j=0; j<c; j++)            {                if(st[i][j]=='F')                {                    q.push(Node(i,j,0));                    fire[i][j]=0,vis[i][j]=1;                }                else if(st[i][j]=='J') stx=i,sty=j;            }        }        prepare();        solve(stx,sty);    }    return 0;}