zoj 1649 Rescue （BFS）（转载）

又是类似骑士拯救公主，不过这个是朋友拯救天使的故事。。。

不同的是，天使有多个朋友，而骑士一般单枪匹马比较帅~

求到达天使的最短时间，杀死一个护卫1 units time ，走一个格子 1 unit time 。SO，杀死一个护卫到达那个格子 2units time。

第一反应是广搜，就搜咧 = =。。

WA了，交hdu上 AC了，hdu数据真弱啊。。。

想了想，想通了，因为一般广搜的话必须都是1个时间才能搜，才能保证这个BFS树是等距离向外伸展的，而这个不是等距离的，所以需要一些处理。

1、我的方法是，找到天使后，把时间比下大小，最后输出最小的。需要优化，只这么做的话，会TLE的，如果走过一个格子，这个格子存走过时候的时间，下次再走到这个格子，如果时间比格子里的短，就入队，否则，就不用入队了。60MS。

2、网上看到另一种方法，就是把杀护卫和走到护卫那个格子看成两个动作等于说是入队两次，这个好啊！！！写了半天终于写出来了。20MS。

3、刚才想起来一种方法，因为如果等距离的BFS的话，队列里的time值是从小往大排的，那我直接用优先队列就可以了哈~~嘻嘻~10MS~人品好，爆0MS了~~

法I

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <string.h>
 5 #include <queue>
 6 #include <limits.h>
 7 #define MAX 205
 8 using namespace std;
 9 typedef struct ANG{
10     int t;
11     int x,y;
12 }ANG;
13 queue <ANG> q;
14 char map[MAX][MAX];
15 int vis[MAX][MAX];
16 int n,m,mmin;
17 int dir[8] = {0,1,0,-1,1,0,-1,0};
18 void BFS()
19 {
20     ANG tmp;
21     int i,x,a,b,aa,bb,t;
22     while( !q.empty() )
23     {
24         tmp = q.front();
25         q.pop();
26         a = tmp.x;
27         b = tmp.y;
28         t = tmp.t;
29         for(i=0; i<8; i+=2)
30         {
31             aa = a + dir[i];
32             bb = b + dir[i+1];
33             if( aa >= 0 && aa < n && bb >=0 && b < m && map[aa][bb] != '#' && vis[aa][bb] )
34             {
35                 if( map[aa][bb] == 'a' )
36                 {
37                     if( t+1 < mmin )
38                         mmin = t+1;
39                     continue;
40                 }
41                     
42                 if( map[aa][bb] == '.' && t+1 < vis[aa][bb] ) //如果走过，而且时间比现在的短，就没必要入队了。 
43                 {
44                     vis[aa][bb] = t+1;
45                     tmp.t = t + 1;
46                     tmp.x = aa;
47                     tmp.y = bb;
48                     q.push(tmp);
49                 }
50                 if( map[aa][bb] == 'x' && t+2 < vis[aa][bb] )
51                 {
52                     vis[aa][bb] = t+2;
53                     tmp.t = t + 2;
54                     tmp.x = aa;
55                     tmp.y = bb;
56                     q.push(tmp);
57                 }
58             }
59         }
60     }
61 }
62 int main()
63 {
64     int i,k,ans;
65     ANG tmp;
66     while( ~scanf("%d%d",&n,&m) )
67     {
68         memset(map,0,sizeof(map));
69         for(i=0; i<n; i++)
70             scanf("%s",map[i]);        
71         
72         while( !q.empty() )
73             q.pop();
74             
75         for(i=0; i<n; i++)
76             for(k=0; k<m; k++)
77                 vis[i][k] = INT_MAX;
78         
79         for(i=0; i<n; i++)
80             for(k=0; k<m; k++)
81                 if( map[i][k] == 'r' )
82                 {
83                     map[i][k] = '.';
84                     tmp.x = i;
85                     tmp.y = k;
86                     tmp.t = 0;
87                     q.push(tmp);
88                     vis[i][k] = 0;
89                 }
90         mmin = INT_MAX;
91         BFS();
92         if( mmin != INT_MAX )
93             printf("%d/n",mmin);
94         else
95             printf("Poor ANGEL has to stay in the prison all his life./n");
96     }
97 return 0;
98 }

法II

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <iostream>
  4 #include <string.h>
  5 #include <queue>
  6 #include <limits.h>
  7 #define MAX 201
  8 using namespace std;
  9 typedef struct ANG{
 10     int t;
 11     int x,y,flag;
 12 }ANG;
 13 char map[MAX][MAX];
 14 int vis[MAX][MAX];
 15 int n,m;
 16 int dir[8] = {0,1,0,-1,1,0,-1,0};
 17 priority_queue<ANG> q;
 18 bool operator<(ANG a, ANG b)
 19 {
 20     return a.t > b.t;
 21 }
 22 int BFS()
 23 {
 24     ANG tmp;
 25     int i,x,a,b,aa,bb,t;
 26     while( !q.empty() )
 27     {
 28         tmp = q.top();
 29         q.pop();
 30         a = tmp.x;
 31         b = tmp.y;
 32         t = tmp.t;
 33         if( map[a][b] == 'x' && tmp.flag == 1 )
 34         {
 35             tmp.x = a;
 36             tmp.y = b;
 37             tmp.t = t+1;
 38             tmp.flag = 2;
 39             q.push(tmp);
 40             vis[a][b] = 1;
 41             continue;
 42         }
 43         for(i=0; i<8; i+=2)
 44         {
 45             aa = a + dir[i];
 46             bb = b + dir[i+1];
 47             if( aa >= 0 && aa < n && bb >=0 && b < m && map[aa][bb] != '#' && !vis[aa][bb] )
 48             {
 49                 if( map[aa][bb] == 'a' )
 50                     return t+1;
 51                     
 52                 if( map[aa][bb] == '.' ) 
 53                 {
 54                     vis[aa][bb] = 1;
 55                     tmp.t = t + 1;
 56                     tmp.x = aa;
 57                     tmp.y = bb;
 58                     q.push(tmp);
 59                 }
 60                 
 61                 if( map[aa][bb] == 'x' )
 62                 {
 63                     vis[aa][bb] = 0;
 64                     tmp.flag = 1;
 65                     tmp.t = t + 1;
 66                     tmp.x = aa;
 67                     tmp.y = bb;
 68                     q.push(tmp);    
 69                 }
 70             }
 71         }
 72     }
 73     return -1;
 74 }
 75 int main()
 76 {
 77     int i,k,ans;
 78     ANG tmp;
 79     while( ~scanf("%d%d",&n,&m) )
 80     {
 81         memset(map,0,sizeof(map));
 82         for(i=0; i<n; i++)
 83             scanf("%s",map[i]);        
 84         
 85         while( !q.empty() )
 86             q.pop();
 87         memset(vis,0,sizeof(vis));
 88         
 89         for(i=0; i<n; i++)
 90             for(k=0; k<m; k++)
 91                 if( map[i][k] == 'r' )
 92                 {
 93                     map[i][k] = '.';
 94                     tmp.x = i;
 95                     tmp.y = k;
 96                     tmp.t = 0;
 97                     q.push(tmp);
 98                     vis[i][k] = 2;
 99                 }
100         ans = BFS();
101         if( ans != -1 )
102             printf("%d/n",ans);
103         else
104             printf("Poor ANGEL has to stay in the prison all his life./n");
105     }
106 return 0;
107 }

法III

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <string.h>
 5 #include <queue>
 6 #include <limits.h>
 7 #define MAX 201
 8 using namespace std;
 9 typedef struct ANG{
10     int t;
11     int x,y;
12 }ANG;
13 char map[MAX][MAX];
14 int vis[MAX][MAX];
15 int n,m;
16 int dir[8] = {0,1,0,-1,1,0,-1,0};
17 priority_queue<ANG> q;
18 bool operator<(ANG a, ANG b)
19 {
20     return a.t > b.t;
21 }
22 int BFS()
23 {
24     ANG tmp;
25     int i,x,a,b,aa,bb,t;
26     while( !q.empty() )
27     {
28         tmp = q.top();
29         q.pop();
30         a = tmp.x;
31         b = tmp.y;
32         t = tmp.t;
33         for(i=0; i<8; i+=2)
34         {
35             aa = a + dir[i];
36             bb = b + dir[i+1];
37             if( aa >= 0 && aa < n && bb >=0 && b < m && map[aa][bb] != '#' && !vis[aa][bb] )
38             {
39                 vis[aa][bb] = 1;
40                 if( map[aa][bb] == 'a' )
41                     return t+1;
42                     
43                 if( map[aa][bb] == '.' ) 
44                 {
45                     tmp.t = t + 1;
46                     tmp.x = aa;
47                     tmp.y = bb;
48                     q.push(tmp);
49                 }
50                 if( map[aa][bb] == 'x'  )
51                 {
52                     tmp.t = t + 2;
53                     tmp.x = aa;
54                     tmp.y = bb;
55                     q.push(tmp);    
56                 }
57             }
58         }
59     }
60     return -1;
61 }
62 int main()
63 {
64     int i,k,ans;
65     ANG tmp;
66     while( ~scanf("%d%d",&n,&m) )
67     {
68         memset(map,0,sizeof(map));
69         for(i=0; i<n; i++)
70             scanf("%s",map[i]);        
71         
72         while( !q.empty() )
73             q.pop();
74         memset(vis,0,sizeof(vis));
75         
76         for(i=0; i<n; i++)
77             for(k=0; k<m; k++)
78                 if( map[i][k] == 'r' )
79                 {
80                     map[i][k] = '.';
81                     tmp.x = i;
82                     tmp.y = k;
83                     tmp.t = 0;
84                     q.push(tmp);
85                     vis[i][k] = 1;
86                 }
87         ans = BFS();
88         if( ans != -1 )
89             printf("%d/n",ans);
90         else
91             printf("Poor ANGEL has to stay in the prison all his life./n");
92     }
93 return 0;
94 }