uva 11624 Fire!（搜索）

开始刷题啦= = 痛并快乐着，学到新东西的感觉其实比看那些无脑的小说、电视剧有意思多了

bfs裸体，关键是先把所有的着火点放入队列，分开一个一个做bfs会超时的

发现vis[][]是多余的，完全可以用num[][]代替了，不过不提交了。。。

uva的submission error跳得我蛋疼，可是介于管理员Carlos及时回复了，还是理解人家吧

  1 #include<cstdio>
  2 #include<cstring>
  3 
  4 const int MAXN=1111;
  5 
  6 struct P{
  7     int x,y;
  8     int c;
  9 };
 10 
 11 P que[MAXN*MAXN];
 12 char mp[MAXN][MAXN];
 13 int num[MAXN][MAXN],vis[MAXN][MAXN];
 14 
 15 int dir[4][2]={1,0,-1,0,0,1,0,-1};
 16 int n,m,flog;
 17 int xi[MAXN],yi[MAXN];
 18 
 19 void bfs(int l,int r)
 20 {
 21     while(l<r)
 22     {
 23         int x=que[l].x;
 24         int y=que[l].y;
 25         int c=que[l++].c;
 26         num[x][y]=c;
 27         for(int i=0;i<4;i++)
 28         {
 29             int dx=x+dir[i][0];
 30             int dy=y+dir[i][1];
 31 
 32             if(dx<0||dy<0||dx>=n||dy>=m){
 33                 if(!flog){
 34                     flog=1;
 35                     que[0].c=c;
 36                 }
 37                 continue;
 38             }
 39             if(!vis[dx][dy]&&mp[dx][dy]!='#'&&(num[dx][dy]>c+1||num[dx][dy]==-1)){
 40                 vis[dx][dy]=1;
 41                 que[r].x=dx;
 42                 que[r].y=dy;
 43                 que[r++].c=c+1;
 44             }
 45         }
 46     }
 47 }
 48 
 49 int main()
 50 {
 51     int T,x,y;
 52     int i,j,k;
 53     int l,r;
 54 
 55     scanf("%d",&T);
 56     while(T--)
 57     {
 58         int tot=0;
 59         scanf("%d%d",&n,&m);
 60         for(i=0;i<n;i++)
 61         {
 62             getchar();
 63             for(j=0;j<m;j++)
 64             {
 65                 scanf("%c",&mp[i][j]);
 66                 if(mp[i][j]=='J'){
 67                     x=i;
 68                     y=j;
 69                 }
 70                 if(mp[i][j]=='F'){
 71                     xi[tot]=i;
 72                     yi[tot++]=j;
 73                 }
 74             }
 75         }
 76 
 77         memset(num,-1,sizeof(num));
 78         memset(vis,0,sizeof(vis));
 79         for(i=0;i<tot;i++)
 80         {
 81             vis[xi[i]][yi[i]]=1;
 82             que[i].x=xi[i];
 83             que[i].y=yi[i];
 84             que[i].c=1;
 85         }
 86         bfs(0,tot);
 87 
 88         memset(vis,0,sizeof(vis));
 89         flog=0;
 90         que[0].x=x;
 91         que[0].y=y;
 92         que[0].c=1;
 93         bfs(0,1);
 94         
 95         if(flog){
 96             printf("%d
",que[0].c);
 97         }else {
 98             printf("IMPOSSIBLE
");
 99         }
100     }
101     return 0;
102 }
103 /*
104 8 8
105 ........
106 ..F...F.
107 ....J...
108 ...F....
109 ......F.
110 ........
111 ........
112 ........
113 
114 5 5
115 .....
116 .###.
117 .#J#.
118 .###.
119 .....
120 
121 5 5
122 .....
123 .#F#.
124 .FJF.
125 .#F#.
126 .....
127 
128 5 5
129 ....F
130 .#.#.
131 ..J..
132 .#.#.
133 F....
134 
135 5 5
136 ....F
137 .#.#.
138 ..J..
139 .#.#.
140 .....
141 */

View Code