uva 11624

直接用bfs做。

代码：

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define FR(i,a,b) for(i=(a);i<(b);i++)
#define FOR(i,n) FR(i,0,n)
#define CLR(x,a) memset(x, a,sizeof(a))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define ABS(a) ((a)<0?-(a):(a))
#define oo 0x7fffffff
#define MAXN 1002
#define MAXQ MAXN*MAXN
typedef long long int64;

char map[MAXN][MAXN];
int que[MAXQ][2];
int dis_j[MAXN][MAXN];
int dis_f[MAXN][MAXN];
int dis[MAXN][MAXN];
int pos[MAXN * 4][2];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int r, c;
int jx, jy;
int fx[MAXQ], fy[MAXQ];
int cnt, nf;
int head, tail;
void bfs(char ch)
{
	int tx, ty, x, y, i, j;
	memset(dis, -1, sizeof(dis));
	head = 0; tail = 0;
	if(ch == 'J')
	{
		que[tail][0] = jx; que[tail++][1] = jy;
		dis[jx][jy] = 0;
	}
	else
	{
		FR(i, 1, nf+1)
		{
			x = fx[i]; y = fy[i];
			dis[x][y] = 0;
			que[tail][0] = x;
			que[tail][1] = y;
			tail++;
		}
	}
	while(head < tail)
	{
		x = que[head][0]; y = que[head][1];
		FOR(i, 4)
		{
			tx = x + dx[i]; ty = y + dy[i];
			if(tx < 0 || tx > r || ty < 0 || ty > c) continue;
			if(dis[tx][ty] != -1) continue;
			if(map[tx][ty] == '#') continue;
			if(map[tx][ty] == 'F') continue;
			dis[tx][ty] = dis[x][y] + 1;
			que[tail][0] = tx; que[tail][1] = ty;
			tail++;
		}
		head++;
	}
}
void init()
{
	int i, j;
	scanf("%d %d", &r, &c);
	getchar();
	cnt = 0; nf = 0;
	FR(i, 1, r + 1)
	{
		FR(j, 1, c + 1)
		{
			map[i][j] = getchar();
			if(map[i][j] == 'J') { jx = i; jy = j;}
			if(map[i][j] == 'F') { nf++; fx[nf] = i; fy[nf] = j;}
			if((i == 1 ||i == r || j == 1 || j == c) && map[i][j] != '#')
			{
				cnt++;
				pos[cnt][0] = i;
				pos[cnt][1] = j;
			}
		}
		getchar();
	}
}
void solve()
{
	int min, i, j, x, y;
	bfs('J');
	memcpy(dis_j, dis, sizeof(dis));
	bfs('F');
	memcpy(dis_f, dis, sizeof(dis));
	min = oo;
	FR(i, 1, cnt + 1)
	{
		x = pos[i][0]; y = pos[i][1];
		if((dis_j[x][y] != -1 && dis_j[x][y] < dis_f[x][y]) || (dis_j[x][y] != -1 && dis_f[x][y] == -1))
		{
			if(min > dis_j[x][y]) min = dis_j[x][y];
		}
	}
	if(min == oo) printf("IMPOSSIBLE\n");
	else printf("%d\n", min + 1);
}
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		init();
		solve();
	}
	return 0;
}