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\n",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\n");

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;

}
巴特西

uva 11624

最新文章

热门文章
