【題目描述】

【題目分析】
看到題目后很清楚是兩個BFS，可是我覺得對于火的BFS可以轉換成判斷，我的做法是將火的位置全部記錄下來，然后判斷某個位置距離每個火的步數是否小于當前步數，可是錯了，還不清楚為什么（有可能是因為沒有記憶化復雜度太高？但是為什么是wa不是超時），改成BFS后就過了
【AC代碼】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<climits>
#include<set>using namespace std;const int MAXN=1005;
int n,m,sx,sy,ans;
char map[MAXN][MAXN];
int vis[MAXN][MAXN];
struct node
{int x,y,step;
}t,p,S;
//struct node1{int x,y;}fire[MAXN*MAXN];
int Time[MAXN][MAXN];
//int cnt;
const int drc[4][2]={1,0,-1,0,0,1,0,-1};
queue<node> fire;/*
bool danger(int x,int y,int step)
{int tmp;for(int i=0;i<cnt;i++){tmp=abs(x-fire[i].x)+abs(y-fire[i].y);if(tmp<=step)return true;}return false;
}
*/void init()
{int u,v;while(!fire.empty()){p=fire.front(); fire.pop();for(int i=0;i<4;i++){u=p.x+drc[i][0]; v=p.y+drc[i][1];if(u<0 || u>n-1 || v<0 || v>m-1) continue;if(map[u][v]=='#') continue;if(p.step+1>=Time[u][v]) continue;Time[u][v]=p.step+1;t.x=u; t.y=v; t.step=p.step+1;fire.push(t);}}
}bool BFS()
{int u,v;memset(vis,0,sizeof(vis));queue<node> q;q.push(S); vis[S.x][S.y]=1;while(!q.empty()){p=q.front(); q.pop();if(p.x==0 || p.x==n-1 || p.y==0 || p.y==m-1){ans=p.step+1;return true;}for(int i=0;i<4;i++){u=p.x+drc[i][0]; v=p.y+drc[i][1];if(u<0 || u>n-1 || v<0 || v>m-1) continue;if(map[u][v]=='#' || vis[u][v]) continue;if(p.step+1>=Time[u][v]) continue;vis[u][v]=1;t.x=u; t.y=v; t.step=p.step+1;q.push(t);}}return false;
}int main()
{int T;scanf("%d",&T);while(T--){while(!fire.empty()) fire.pop();memset(map,0,sizeof(map));scanf("%d%d",&n,&m);//cnt=0; ans=0;memset(Time,0x3f,sizeof(Time));for(int i=0;i<n;i++){scanf("%s",map[i]);for(int j=0;j<m;j++){if(map[i][j]=='J'){S.x=i; S.y=j; S.step=0;map[i][j]='.';}else if(map[i][j]=='F'){//fire[cnt].x=i; fire[cnt].y=j;//map[i][j]='#';//cnt++;t.x=i; t.y=j; t.step=0;Time[i][j]=0;fire.push(t);}}}init();if(BFS()){printf("%d\n",ans);}else{printf("IMPOSSIBLE\n");}}return 0;
}

剛才記憶化了一下試了一下還是不行，并不知道為什么
【wa代碼】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<climits>
#include<set>using namespace std;const int MAXN=1005;
int n,m,sx,sy,ans;
char map[MAXN][MAXN];
int vis[MAXN][MAXN];
struct node
{int x,y,step;
}t,p,S;
struct node1{int x,y;}fire[MAXN*MAXN];
int Time[MAXN][MAXN];
int cnt;
const int drc[4][2]={1,0,-1,0,0,1,0,-1};
//queue<node> fire;/*
bool danger(int x,int y,int step)
{int tmp;for(int i=0;i<cnt;i++){tmp=abs(x-fire[i].x)+abs(y-fire[i].y);if(tmp<=step)return true;}return false;
}
*/void init()
{int u,v;/*while(!fire.empty()){p=fire.front(); fire.pop();for(int i=0;i<4;i++){u=p.x+drc[i][0]; v=p.y+drc[i][1];if(u<0 || u>n-1 || v<0 || v>m-1) continue;if(map[u][v]=='#') continue;if(p.step+1>=Time[u][v]) continue;Time[u][v]=p.step+1;t.x=u; t.y=v; t.step=p.step+1;fire.push(t);}}*/for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(map[i][j]=='#') continue;for(int k=0;k<cnt;k++){Time[i][j]=min(Time[i][j],abs(i-fire[k].x)+abs(j-fire[k].y));}}}
}bool BFS()
{int u,v;memset(vis,0,sizeof(vis));queue<node> q;q.push(S); vis[S.x][S.y]=1;while(!q.empty()){p=q.front(); q.pop();if(p.x==0 || p.x==n-1 || p.y==0 || p.y==m-1){ans=p.step+1;return true;}for(int i=0;i<4;i++){u=p.x+drc[i][0]; v=p.y+drc[i][1];if(u<0 || u>n-1 || v<0 || v>m-1) continue;if(map[u][v]=='#' || vis[u][v]) continue;if(p.step+1>=Time[u][v]) continue;vis[u][v]=1;t.x=u; t.y=v; t.step=p.step+1;q.push(t);}}return false;
}void show()
{for(int i=0;i<cnt;i++){printf("%d %d\n",fire[i].x,fire[i].y);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){printf("%d ",Time[i][j]);}printf("\n");}
}int main()
{int T;scanf("%d",&T);while(T--){//while(!fire.empty()) fire.pop();memset(map,0,sizeof(map));scanf("%d%d",&n,&m);cnt=0; ans=0;memset(fire,0,sizeof(fire));memset(Time,0x3f,sizeof(Time));for(int i=0;i<n;i++){scanf("%s",map[i]);for(int j=0;j<m;j++){if(map[i][j]=='J'){S.x=i; S.y=j; S.step=0;map[i][j]='.';}else if(map[i][j]=='F'){fire[cnt].x=i; fire[cnt].y=j;cnt++;//t.x=i; t.y=j; t.step=0;//Time[i][j]=0;//fire.push(t);}}}init();//show();if(BFS()){printf("%d\n",ans);}else{printf("IMPOSSIBLE\n");}}return 0;
}