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

 

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

 

求到达天使的最短时间，杀死一个护卫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

 

#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 205 using namespace std; typedef struct ANG{ int t; int x,y; }ANG; queue <ANG> q; char map[MAX][MAX]; int vis[MAX][MAX]; int n,m,mmin; int dir[8] = {0,1,0,-1,1,0,-1,0}; void BFS() { ANG tmp; int i,x,a,b,aa,bb,t; while( !q.empty() ) { tmp = q.front(); q.pop(); a = tmp.x; b = tmp.y; t = tmp.t; for(i=0; i<8; i+=2) { aa = a + dir[i]; bb = b + dir[i+1]; if( aa >= 0 && aa < n && bb >=0 && b < m && map[aa][bb] != '#' && vis[aa][bb] ) { if( map[aa][bb] == 'a' ) { if( t+1 < mmin ) mmin = t+1; continue; } if( map[aa][bb] == '.' && t+1 < vis[aa][bb] ) //如果走过，而且时间比现在的短，就没必要入队了。 { vis[aa][bb] = t+1; tmp.t = t + 1; tmp.x = aa; tmp.y = bb; q.push(tmp); } if( map[aa][bb] == 'x' && t+2 < vis[aa][bb] ) { vis[aa][bb] = t+2; tmp.t = t + 2; tmp.x = aa; tmp.y = bb; q.push(tmp); } } } } } int main() { int i,k,ans; ANG tmp; while( ~scanf("%d%d",&n,&m) ) { memset(map,0,sizeof(map)); for(i=0; i<n; i++) scanf("%s",map[i]); while( !q.empty() ) q.pop(); for(i=0; i<n; i++) for(k=0; k<m; k++) vis[i][k] = INT_MAX; for(i=0; i<n; i++) for(k=0; k<m; k++) if( map[i][k] == 'r' ) { map[i][k] = '.'; tmp.x = i; tmp.y = k; tmp.t = 0; q.push(tmp); vis[i][k] = 0; } mmin = INT_MAX; BFS(); if( mmin != INT_MAX ) printf("%d/n",mmin); else printf("Poor ANGEL has to stay in the prison all his life./n"); } return 0; }  

 

法II

 

#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 201 using namespace std; typedef struct ANG{ int t; int x,y,flag; }ANG; char map[MAX][MAX]; int vis[MAX][MAX]; int n,m; int dir[8] = {0,1,0,-1,1,0,-1,0}; priority_queue<ANG> q; bool operator<(ANG a, ANG b) { return a.t > b.t; } int BFS() { ANG tmp; int i,x,a,b,aa,bb,t; while( !q.empty() ) { tmp = q.top(); q.pop(); a = tmp.x; b = tmp.y; t = tmp.t; if( map[a][b] == 'x' && tmp.flag == 1 ) { tmp.x = a; tmp.y = b; tmp.t = t+1; tmp.flag = 2; q.push(tmp); vis[a][b] = 1; continue; } for(i=0; i<8; i+=2) { aa = a + dir[i]; bb = b + dir[i+1]; if( aa >= 0 && aa < n && bb >=0 && b < m && map[aa][bb] != '#' && !vis[aa][bb] ) { if( map[aa][bb] == 'a' ) return t+1; if( map[aa][bb] == '.' ) { vis[aa][bb] = 1; tmp.t = t + 1; tmp.x = aa; tmp.y = bb; q.push(tmp); } if( map[aa][bb] == 'x' ) { vis[aa][bb] = 0; tmp.flag = 1; tmp.t = t + 1; tmp.x = aa; tmp.y = bb; q.push(tmp); } } } } return -1; } int main() { int i,k,ans; ANG tmp; while( ~scanf("%d%d",&n,&m) ) { memset(map,0,sizeof(map)); for(i=0; i<n; i++) scanf("%s",map[i]); while( !q.empty() ) q.pop(); memset(vis,0,sizeof(vis)); for(i=0; i<n; i++) for(k=0; k<m; k++) if( map[i][k] == 'r' ) { map[i][k] = '.'; tmp.x = i; tmp.y = k; tmp.t = 0; q.push(tmp); vis[i][k] = 2; } ans = BFS(); if( ans != -1 ) printf("%d/n",ans); else printf("Poor ANGEL has to stay in the prison all his life./n"); } return 0; }  

 

法III

 

#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 201 using namespace std; typedef struct ANG{ int t; int x,y; }ANG; char map[MAX][MAX]; int vis[MAX][MAX]; int n,m; int dir[8] = {0,1,0,-1,1,0,-1,0}; priority_queue<ANG> q; bool operator<(ANG a, ANG b) { return a.t > b.t; } int BFS() { ANG tmp; int i,x,a,b,aa,bb,t; while( !q.empty() ) { tmp = q.top(); q.pop(); a = tmp.x; b = tmp.y; t = tmp.t; for(i=0; i<8; i+=2) { aa = a + dir[i]; bb = b + dir[i+1]; if( aa >= 0 && aa < n && bb >=0 && b < m && map[aa][bb] != '#' && !vis[aa][bb] ) { vis[aa][bb] = 1; if( map[aa][bb] == 'a' ) return t+1; if( map[aa][bb] == '.' ) { tmp.t = t + 1; tmp.x = aa; tmp.y = bb; q.push(tmp); } if( map[aa][bb] == 'x' ) { tmp.t = t + 2; tmp.x = aa; tmp.y = bb; q.push(tmp); } } } } return -1; } int main() { int i,k,ans; ANG tmp; while( ~scanf("%d%d",&n,&m) ) { memset(map,0,sizeof(map)); for(i=0; i<n; i++) scanf("%s",map[i]); while( !q.empty() ) q.pop(); memset(vis,0,sizeof(vis)); for(i=0; i<n; i++) for(k=0; k<m; k++) if( map[i][k] == 'r' ) { map[i][k] = '.'; tmp.x = i; tmp.y = k; tmp.t = 0; q.push(tmp); vis[i][k] = 1; } ans = BFS(); if( ans != -1 ) printf("%d/n",ans); else printf("Poor ANGEL has to stay in the prison all his life./n"); } return 0; }