学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1242

//搜索题：广度优先搜索
/*
当前格视为节点，其上下左右视为下一层，用广度优先搜索，将每层的节点入队。对已经访
问的格子标记已经访问。节点附带属性为坐标和时间，由于有守卫影响，所以同一个格子可
能出现不同的时间属性，故将守卫的格子视为两层，对守卫的格子进行标记，以确定是否为
第一次访问将其入队两次。最后，访问到目的地时候break退出
*/
#include <iostream>
#include <queue>
using namespace std;
struct  Pos
{
	int i, j, time;
};
int main()
{
	char M[200][200]; // 监狱
	int n, m;
	int time, bi, bj, i, j;
	bool visited[200][200], x[200][200], flag;
	int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
	queue<Pos> q;
	Pos v;
	while (cin >> n >> m) {
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++) {
				cin >> M[i][j];
				if (M[i][j] == 'r') {bi = i; bj = j;}
				visited[i][j] = false;
				if (M[i][j] == 'x') x[i][j] = true;
			}
		while (!q.empty())//清空上次监狱地图
			q.pop();
		flag = false;
		v.i = bi; v.j = bj; v.time = 0;
		q.push(v);
		visited[bi][bj] = true;//标记初始点已访问
		while (!q.empty()) {
			v = q.front();
			q.pop();
			i = v.i;
			j = v.j;
			time = v.time;
			if (M[i][j] == 'a') {flag = true; break;}//到达目的地
			if (M[i][j] == 'x' && x[i][j]) {//首次遇到该守卫,
				x[i][j] = false;
				v.time = time+1;//再次将他入队，因为他需要多消耗一个时间
				q.push(v);
				continue;
			}
			int k;
			for (k = 0; k < 4; k++) { //访问下一层点
				if (M[i + dir[k][0]][j + dir[k][1]] != '#' && 
					!visited[i + dir[k][0]][j + dir[k][1]] && 
					(i + dir[k][0]) >= 0 && (j + dir[k][1]) >= 0 && 
					(i + dir[k][0]) < n && (j + dir[k][1]) < m ) 
				{
					if (M[i + dir[k][0]][j + dir[k][0]] == 'x')//如果是守卫的点
							x[i + dir[k][0]][j + dir[k][1]] = true;
					v.i = i + dir[k][0]; v.j = j + dir[k][1]; v.time = time+1;//将当前点入队
					q.push(v);
					visited[i + dir[k][0]][j + dir[k][1]] = true;//标记已访问
				}
			}
		}
		if (flag)
			cout << time << endl;
		else
			cout << "Poor ANGEL has to stay in the prison all his life." << endl;
	}
	return 0;
}