UVA 11624 Fire! BFS+技巧

大緻題意：

有意思的一道搜尋題，大意是說一個人在森林裡，森林裡着火了，問能不能走出去。

其中’F’代表火源，可能不止一個，然後火勢會向上下左右四個方向蔓延。

解題思路：

将’F’火源先放入隊列，再把人物所在位置放隊列中，這樣就像回合制遊戲一樣，火勢先手，處理好蔓延的火勢，又放入隊列中，接着再處理人。

AC代碼：

#include<bits/stdc++.h>
using namespace std;
struct node{
   int x,y,k;
   node() {
      x=;y=;k=;
   };
};
char s[][];
int dx[]={,,,-};
int dy[]={,-,,};
int n,m;
queue<node> q;
bool vis[][];
int bfs()
{
    memset(vis,,sizeof(vis));
    node t,tt;
    bool ok=false;
    while(!q.empty())
    {
        t=q.front();q.pop();
        if(t.k!=-&&(t.x==||t.y==||t.x==m-||t.y==n-)) {
            ok=true;break;
        }
            for(int i=;i<;i++)
            {
                int xx=t.x+dx[i];
                int yy=t.y+dy[i];
                if(t.k==-) {
                    if(xx<m&&xx>=&&yy>=&&yy<n&&s[xx][yy]!='#'&&s[xx][yy]!='F')
                    {
                        zk=true;
                        node tt;
                        tt.x=xx;tt.y=yy;tt.k=-;
                        s[tt.x][tt.y]='F';
                        q.push(tt);
                    }
                }
                else {
                    if(s[xx][yy]=='.'&&!vis[xx][yy]) {
                            zk=true;
                        node tt;
                        vis[xx][yy]=;
                        tt.x=xx;tt.y=yy;tt.k=t.k+;
                        q.push(tt);
                    }
                }
            }
    }
    if(ok) return t.k+;
    else return ;
}
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
       cin>>m>>n;
       while(!q.empty()) q.pop();
       int x,y;
       for(int i=;i<m;i++) scanf("%s",s[i]);
       for(int i=;i<m;i++)
        for(int j=;j<n;j++)
       {
           if(s[i][j]=='F') {
            node t;
            t.x=i;t.y=j;t.k=-;
            q.push(t);
           }
           if(s[i][j]=='J') {
            x=i;y=j;
           }
       }
       node t;t.x=x;t.y=y;t.k=;
       q.push(t);
       int z=bfs();
       if(z) cout<<z<<endl;
       else cout<<"IMPOSSIBLE"<<endl;
   }
}