UVA - 11624 Fire! 双BFS

还是不叫简单的BFS.在这里贴下代码,重要理解思想.

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define db double
using namespace std;
const int maxn=1e3+5;
int fx[1000005],fy[1000005];
char maze[maxn][maxn];
int vis[maxn][maxn];
int mx,my;
int cnt=0;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int r,c;
struct point
{
    int x,y,t;
    int type;
};

bool judge(point a)
{
    if(a.type==1)
    {
        if(maze[a.x][a.y]!='#' && vis[a.x][a.y]==0 )//之所以人没加越界条件,因为结束条件是刚好人站在迷宫的最外一层,即这个迷宫在外面是还有一层的.
            return true;//只能用!='#' 而不能用=='.'因为我们是要求人是要走出去的,而前者的判定条件人才能走出去,而后者人就不能走出去了.
        return false;
    }
    else if(a.type==2)
    {
        if(a.x>=1 && a.y >=1 && a.x<=r && a.y<=c && maze[a.x][a.y]!='#' && vis[a.x][a.y]!=2)//只不能走走过的点.
            return true;//而火是不能走出去的.这个条件也可以合并为if(maze[a.x][a.y]=='.' && vis[a.x][a.y]!=2)
        return false;
    }
}

int bfs()
{
    point a;
    queue<point>q;
    a.x=mx,a.y=my;
    a.t=0,a.type=1;
    vis[a.x][a.y]=a.type;
    q.push(a);
    for(int i=0;i<cnt;i++)
    {
        point v;
        v.x=fx[i],v.y=fy[i];
        v.t=0,v.type=2;
        vis[v.x][v.y]=v.type;
        q.push(v);
    }
    while(!q.empty())
    {
        point b=q.front();
        q.pop();
        if((b.x==0 || b.y==0 || b.x==r+1 || b.y==c+1) && b.type==1){

            /*for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    printf("%d ",vis[i][j]);
                }
                printf("\n");
            }*/
            return b.t;
        }
        if( b.type==1 && vis[b.x][b.y]==2)
            continue;
        for(int i=0;i<4;i++){
            point s;
            s.x=b.x+dir[i][0];
            s.y=b.y+dir[i][1];
            s.type = b.type;
            if(judge(s)){
                s.t=b.t+1;
                vis[s.x][s.y]=s.type;
                q.push(s);
            /*for(int i=1;i<=r;i++){
                for(int j=1;j<=c;j++){
                    printf("%d ",vis[i][j]);
                }
                printf("\n");
            }
            printf("\n\n\n");*/
            }
        }
    }
    /*for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            printf("%d ",vis[i][j]);
        }
        printf("\n");
    }*/
    return 0;
}
int main()//这个方法也行,就是稍微难懂点.不过写出来就明白了.
{
    int t;
    scanf("%d",&t);
    while(t--){
    memset(maze,0,sizeof(maze));
    memset(fx,0,sizeof(fx));
    memset(fy,0,sizeof(fy));
    memset(vis,0,sizeof(vis));
        scanf("%d %d",&r,&c);
        getchar();
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                scanf("%c",&maze[i][j]);
            }
            getchar();
        }
        /*for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                printf("%c",maze[i][j]);
            }
            printf("\n");
        }*/
        point a;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                if(maze[i][j]=='F'){
                    fx[cnt]=i;
                    fy[cnt]=j;
                    cnt++;
                }
                else if(maze[i][j]=='J'){
                    mx=i;
                    my=j;
                }
            }
        }
        int ans=bfs();
        if(ans) cout << ans<<endl;
        else cout << "IMPOSSIBLE" <<endl;
    }
}

如果不是很懂的话,就把我注释的地方划去,把每一步打出来看就知道意思了.