uva 11624

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define N 1100
struct nodde {
int x,y;
}f[N],start;
int h,n,m,visitt[N][N];
int dis[4][2]={-1,0,1,0,0,1,0,-1};
char str[N][N];
struct node {
int x,y,time,f;
};
int judge(int x,int y) {
if(x>=1&&x<=n&&y>=1&&y<=m&&str[x][y]!='#'&&!visitt[x][y])
    return 1;
return 0;
}
void bfs() {
int i;
queue<node>q;
node cur,next;
memset(visitt,0,sizeof(visitt));
for(i=0;i<h;i++) {
    cur.x=f[i].x;
    cur.y=f[i].y;
    cur.time=0;
    cur.f=1;
    q.push(cur);
    visitt[cur.x][cur.y]=1;
}
cur.x=start.x;
cur.y=start.y;
cur.time=0;
cur.f=0;
q.push(cur);
while(!q.empty()) {
    cur=q.front();
      if((cur.x==1||cur.x==n||cur.y==1||cur.y==m)&&cur.f==0) {//有可能起点就在边界上
            printf("%d
",cur.time+1);
            return ;
        }
    q.pop();
    for(i=0;i<4;i++) {
        int xx=next.x=cur.x+dis[i][0];
        int yy=next.y=cur.y+dis[i][1];
        next.time=cur.time+1;
        next.f=cur.f;
        if(judge(xx,yy)) {
        visitt[xx][yy]=1;
            q.push(next);
        }
    }
}
printf("IMPOSSIBLE
");
return ;
}
int main() {
    int i,j,t;
    scanf("%d",&t);
    while(t--) {
     scanf("%d%d",&n,&m);
     for(i=1;i<=n;i++)
        scanf("%s",str[i]+1);
        h=0;
     for(i=1;i<=n;i++)
     for(j=1;j<=m;j++) {
        if(str[i][j]=='J')
            start.x=i,start.y=j;
        if(str[i][j]=='F') {
            f[h].x=i;
            f[h++].y=j;
        }
     }
    bfs();
    }
return 0;
}
原文地址:https://www.cnblogs.com/thefirstfeeling/p/4410777.html