uva11624Fire!（bfs）

Fire!

第一次bfs预处理出火源烧到各点的最短时间dead[][]; 注意多起点(也可能没有火）。
第二次从起点bfs，到边界返回步数加1; 单起点。
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 using namespace std;
  5 const int maxn=1050;
  6 char pic[maxn][maxn];
  7 int vis[maxn][maxn];
  8 int dead[maxn][maxn];
  9 int n,m;
 10 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 11 struct node
 12 {
 13     int x,y;
 14     int st;
 15     node(int x,int y,int st):x(x),y(y),st(st){}
 16     node(){};
 17 }now,nex;
 18 
 19 queue<node>q;
 20 bool inside(node no)
 21 {
 22     if(no.x>=0&&no.x<n&&no.y>=0&&no.y<m) return 1;
 23     return 0;
 24 }
 25 void bfs1()
 26 {
 27     
 28     for(int i=0;i<n;i++)
 29         for(int j=0;j<m;j++)
 30             dead[i][j]=0x3f3f3f3f;   //开始没有初始化，WA了n次才意识到可能没有火源。
 31         memset(vis,0,sizeof(vis));
 32     while(!q.empty()) q.pop();
 33     for(int i=0;i<n;i++)
 34         for(int j=0;j<m;j++)
 35             if(pic[i][j]=='F')
 36             {
 37                 q.push(node(i,j,0));
 38                 dead[i][j]=0;
 39                 vis[i][j]=1;
 40             }
 41     while(!q.empty())
 42     {
 43         now=q.front();
 44         q.pop();
 45         for(int i=0;i<4;i++)
 46         {
 47             nex.x=now.x+dir[i][0];
 48             nex.y=now.y+dir[i][1];
 49             if(inside(nex)&&!vis[nex.x][nex.y]&&pic[nex.x][nex.y]!='#')
 50             {
 51                 vis[nex.x][nex.y]=1;
 52                 dead[nex.x][nex.y]=dead[now.x][now.y]+1;
 53                 q.push(nex);
 54             }
 55         }
 56 
 57     }
 58     return ;
 59 }
 60 int bfs2()
 61 {
 62     while(!q.empty()) q.pop();
 63     memset(vis,0,sizeof(vis));
 64     for(int i=0;i<n;i++)
 65         for(int j=0;j<m;j++)
 66             if(pic[i][j]=='J') 
 67             {
 68                 q.push(node(i,j,0));
 69                 vis[i][j]=1;
 70                 break;
 71             }
 72     while(!q.empty())
 73     {
 74         now=q.front();
 75         q.pop();
 76         if(now.x==0||now.x==n-1||now.y==0||now.y==m-1) return now.st+1;
 77         for(int i=0;i<4;i++)
 78         {
 79             nex.x=now.x+dir[i][0];
 80             nex.y=now.y+dir[i][1];
 81             nex.st=now.st+1;
 82             if(inside(nex)&&!vis[nex.x][nex.y]&&pic[nex.x][nex.y]!='#'&&nex.st<dead[nex.x][nex.y])
 83             {
 84                 vis[nex.x][nex.y]=1;
 85                 q.push(nex);
 86             }
 87         }
 88     }
 89     return -1;
 90 
 91 }
 92 int main()
 93 {
 94     int t;
 95     scanf("%d",&t);
 96     while(t--)
 97     {
 98         scanf("%d%d",&n,&m);
 99         for(int i=0;i<n;i++)
100             scanf("%s",pic[i]);
101         bfs1();
102         int ans=bfs2();
103         if(ans!=-1) printf("%d
",ans);
104         else puts("IMPOSSIBLE");
105 
106     }
107 }