From Evernote:

uva 11624

幫助Joe別被火燒到然後跑出去，標準BFS作法

浪費了一整天
RTE跟TLE交錯顯示....

最後原來是界線沒考慮好
input:
4
10 10
##########
#.....JFF#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
..########
3 1
#
J
F
1 2
.J
5 5
#####
#..F#
#.J.#
....F
#####

[sourcecode language="cpp"]

//============================================================================
// Name : Fire!.cpp
// Date : 2013 2013/1/28 下午6:23:57
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\
printf("%d ",dp[htx][hty]);}Pln();}
#define M 1100
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
using namespace std;
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
struct pile{
int x,y,tim,fire;
};
pile q[M*M],john,fir[M*M];
char mz[M][M];
bool vis[M][M];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int bx,by;
int ck;
int bfs(){
int front,rear;
front=rear=0;
for(int i=0;i<ck;i++)
q[front++]=fir[i];
q[front++]=john;
while(front>rear){
pile &pmp=q[rear++];
if(pmp.fire){
for(int i=0;i<4;i++){
int x=pmp.x+dx[i];
int y=pmp.y+dy[i];
if(x>=0&&x<bx&&y>=0&&y<by&&(!vis[x][y])){
vis[x][y]=1;
q[front].x=x;
q[front].y=y;
q[front].tim=pmp.tim+1;
q[front++].fire=1;
}
}
}
else if(mz[pmp.x][pmp.y]=='J'){
for(int i=0;i<4;i++){
int x=pmp.x+dx[i];
int y=pmp.y+dy[i];
if(x==-1||y==-1)return pmp.tim+1;
if(!vis[x][y]){
// printf("%d %d v%d\n",x,y,vis[x][y]);
mz[x][y]='J';
vis[x][y]=1;
q[front].x=x;
q[front].y=y;
q[front].tim=pmp.tim+1;
q[front].fire=0;
if(!(x>=0&&x<bx&&y>=0&&y<by))return q[front].tim;
front++;
}
}
}
}
return -1;
}

int main() {
ios_base::sync_with_stdio(0);
int test;
scanf("%d",&test);
while(test--){
Set(vis,false);
Set(mz,'.');
scanf("%d%d",&by,&bx);
ck=0;
for(int i=0;i<by;i++){
getchar();
for(int j=0;j<bx;j++){
mz[j][i]=getchar();
switch(mz[j][i]){
case 'J':
vis[j][i]=1;
john.fire=0;
john.x=j;
john.y=i;
john.tim=0;
break;
case 'F':
vis[j][i]=1;
fir[ck].fire=1;
fir[ck].x=j;
fir[ck].y=i;
fir[ck].tim=0;
ck++;
break;
case '#':
vis[j][i]=1;
break;
}
}

}
int ans=bfs();
if(ans==-1)printf("IMPOSSIBLE\n");
else{
printf("%d\n",ans);
}
}

}

[/sourcecode]