又是类似骑士拯救公主，不过这个是朋友拯救天使的故事。。。
不同的是，天使有多个朋友，而骑士一般单枪匹马比较帅~
求到达天使的最短时间，杀死一个护卫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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define MAX 205 8 using namespace std; 9 typedef struct ANG{10 int t;11 int x,y;12 }ANG;13 queue 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
法II
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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 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
法III
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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 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