LA 5966 Blade and Sword (双向bfs + 想法) - from lanshui_Yang
题目大意：给你一张有n * m个网格的图，每个网格可能是如下符号：
“#”：墙
“P”：出发点
“D”：终点
“.”：空地
“*”：传送机
有一个旅行家（假设名叫Mike），他要从点P到达点D，途中必须遵循如下规则：
1、 Mike可以走到空地（“.”），但不可通过墙（“#”）。
2、 Mike也可以走到传送机（“*”），但是当他第一次到达传送机时，下一步只有一种选择：他必须选择到达另一个传送机，然后，下一步会有两种选择：
一、走到相邻的可去的格子中。
二、选择到达另一个传送机，然后遵循同样的规则。
让你计算出Mike从点P到点D的最少步数，如果不能到达，就输出“impossible”。
解题思路：Mike从点P到达点D只可能有两种方式：
1、 经过传送机（“*”）， 但图中必须有两个或两个以上的传送机。
2、 不经过传送机，只经过空地（“.”）。
所以只需找出两种方式所需步数的最小值即可。
Ps：程序后面有几组我自己的测试样例，请仔细理解。
具体解法请看程序：
#include <set>#include <map>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <string>#include <vector>#include <iomanip>#include <cstring>#include <iostream>#include <algorithm>#define PI acos(-1.0)#define inf 0x3fffffff#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int MAXN = 205 ;char s[MAXN][MAXN] ;bool vis[MAXN][MAXN] ;int dP[MAXN][MAXN] ; // 记录点P到每个点网格中每个点（中间不经过“*”）的最短距离int dD[MAXN][MAXN] ; // 记录点D到每个点网格中每个点（中间不经过“*”）的最短距离int ci[MAXN][MAXN] ; // 记录每个“*”点是否能从点P或点D到达。int ca ;int m , n ;int te ; // 统计矩阵中的 “*” 数量。int X[4] = {0 , 0 , 1 , -1} ; // 四个方向int Y[4] = {1 , -1 , 0 , 0} ;int MIN ; // 记录从点P 到 点D 距离的最小值struct Node{ int x ; int y ;};Node c , e ; // c代表点P ，e 代表 点Dstruct Kx // 记录 每个可达的 “*”到点P 和 到点D的最近距离{ int x ; int y ; int d ;} kkP[MAXN * MAXN] , kkD[MAXN * MAXN] ;int cntP , cntD ;void init() // 输入{ scanf("%d%d" , &m , &n) ; mem(ci , 0) ; int i , j ; te = 0 ; for(i = 0 ; i < m ; i ++) { scanf("%s" , s[i]) ; for(j = 0 ; j < n ; j ++) { if(s[i][j] == '*') { te ++ ; } else if(s[i][j] == 'P') { c.x = i ; c.y = j ; } else if(s[i][j] == 'D') { e.x = i ; e.y = j ; } } }}queue<Node> q ;int cango1(int x , int y){ if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && ((s[x][y] == '.' || s[x][y] == 'D'))) return 1 ; return 0 ;}int cango2(int x , int y){ if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && s[x][y] != '#') return 1 ; return 0 ;}bool flag ; // 判断点P是否能不经过点 “*” 到达 点D 。void bfs(int i , int j , int bb) // 从点P bfs{ while (!q.empty()) q.pop() ; Node tmp ; tmp.x = i ; tmp.y = j ; q.push(tmp) ; vis[i][j] = true ; while (!q.empty()) { tmp = q.front() ; q.pop() ; int k ; int tx , ty ; for(k = 0 ; k < 4 ; k ++) { Node tp2 ; tx = tmp.x + X[k] ; ty = tmp.y + Y[k] ; if(bb == 1) { if(cango1(tx , ty)) { dP[tx][ty] = dP[tmp.x][tmp.y] + 1 ; if(tx == e.x && ty == e.y) flag = true ; vis[tx][ty] = true ; tp2.x = tx ; tp2.y = ty ; q.push(tp2) ; } } else { if(cango2(tx , ty)) { dP[tx][ty] = dP[tmp.x][tmp.y] + 1 ; if(s[tx][ty] == '*') { ci[tx][ty] ++ ; ++ cntP ; kkP[cntP].x = tx ; kkP[cntP].y = ty ; kkP[cntP].d = dP[tx][ty] ; } if(tx == e.x && ty == e.y) flag = true ; vis[tx][ty] = true ; tp2.x = tx ; tp2.y = ty ; if(s[tx][ty] != '*') // 注意此处 q.push(tp2) ; } } } }}void bfs2(int i , int j ) // 从点D bfs{ while (!q.empty()) q.pop() ; Node tmp ; tmp.x = i ; tmp.y = j ; q.push(tmp) ; vis[i][j] = true ; while (!q.empty()) { tmp = q.front() ; q.pop() ; int k ; int tx , ty ; for(k = 0 ; k < 4 ; k ++) { Node tp2 ; tx = tmp.x + X[k] ; ty = tmp.y + Y[k] ; if(cango2(tx , ty)) { dD[tx][ty] = dD[tmp.x][tmp.y] + 1 ; if(s[tx][ty] == '*') { ci[tx][ty] ++ ; ++ cntD ; kkD[cntD].x = tx ; kkD[cntD].y = ty ; kkD[cntD].d = dD[tx][ty] ; } vis[tx][ty] = true ; tp2.x = tx ; tp2.y = ty ; if(s[tx][ty] != '*') // 注意此处 q.push(tp2) ; } } }}void solve(){ printf("Case %d: " , ++ ca) ; flag = false ; mem(dP , 0) ; mem(dD , 0) ; mem(vis , 0) ; cntP = cntD = -1 ; if(te <= 1) { bfs(c.x , c.y , 1) ; } else { bfs(c.x , c.y , 2) ; mem(vis , 0) ; bfs2(e.x , e.y) ; } int i , j ; MIN = inf ; if(te > 1) // 注意此处，想一想 { for(i = 0 ; i < m ; i ++) { for(j = 0 ; j < n ; j ++) { if(ci[i][j] > 1) { if(MIN > dP[i][j] + dD[i][j] + 2) MIN = dP[i][j] + dD[i][j] + 2 ; } } } } if(flag) { if(te <= 1) { if(MIN > dP[e.x][e.y]) MIN = dP[e.x][e.y] ; printf("%d\n" , MIN) ; } else { MIN = min(MIN , dP[e.x][e.y]) ; if(cntP >= 0 && cntD >= 0) { if(kkD[0].x == kkP[0].x && kkD[0].y == kkP[0].y) { if(cntP > 0) { MIN = min(MIN , kkP[1].d + kkD[0].d + 1) ; } if(cntD > 0) { MIN = min(MIN , kkP[0].d + kkD[1].d + 1) ; } } else { MIN = min(MIN , kkD[0].d + kkP[0].d + 1) ; } } printf("%d\n" , MIN) ; } } else { if(te <= 1) { puts("impossible") ; return ; } else { if(cntP < 0 || cntD < 0) { puts("impossible") ; return ; } if(kkD[0].x == kkP[0].x && kkD[0].y == kkP[0].y) { if(cntP > 0) { MIN = min(MIN , kkP[1].d + kkD[0].d + 1) ; } if(cntD > 0) { MIN = min(MIN , kkP[0].d + kkD[1].d + 1) ; } } else { MIN = min(MIN , kkD[0].d + kkP[0].d + 1) ; } printf("%d\n" , MIN) ; return ; } }}int main(){ int T ; scanf("%d" , &T) ; while (T --) { init() ; solve() ; } return 0 ;}/*94 10###########.P..#*..##*......D###########3 9##########P.#..D.##########3 7########P*D#*########3 8########P*.#..D#####*###3 5######P.D######3 5######P*D######3 5######P..######5 10###########.P..#*..##.....#####*......D###########3 9##########P*D...*##########*/