P1825 [USACO11OPEN]Corn Maze S

题意：

奶牛们去一个 N\times MN×M 玉米迷宫，2 \leq N \leq 300,2 \leq M \leq3002≤N≤300,2≤M≤300。

迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。

如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。

玉米迷宫除了唯一的一个出口都被玉米包围。

迷宫中的每个元素都由以下项目中的一项组成：

1. 玉米，# 表示，这些格子是不可以通过的。
2. 草地，. 表示，可以简单的通过。
3. 传送装置，每一对大写字母 \tt{A}A 到 \tt{Z}Z 表示。
4. 出口，= 表示。
5. 起点， @ 表示

奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 11 个单位时间。从装置的一个结点到另一个结点不花时间。

输入：

5 6
###=##
#.W.##
#.####
#[email protected]##
######

输出：

3

思路：根据题意可以用bfs解决，需要特别注意的是到达传送点时需要特殊处理，传送点之间不需要标记，因为传送点可能需要用多次。例如样例：

3 5
A#@A=
.#.#.
.....

 此时的走法是1,3 ->1,4->1,1->2,1->1,1->1,4->1,5。因为传送不需要时间，所以一共需要4单位的时间，此时传送门被重复使用了两次。所以传送门不需要标记。那么怎么放置在传送门之间来回走导致死循环呢？这个问题不需要担心，因为我到达传送门，那么我会标记传送门周围的点为true。然后我的dx和dy数组只有走上下左右4个方向的状态，并没有直接传送的状态。所以传送门之间并不会直接传送，而是需要你走出传送门然后走进传送门才能进行传送，所以并不会出现死循环。

那么这样我们就可以愉快的AC了，code如下：

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII; 

const int N = 500;

int n, m, Sx, Sy, Ex, Ey, dist[N][N];
char g[N][N];
bool vis[N][N];

PII _flash(int x, int y)
{
	PII t;
	for(int i = 1; i <= n; i ++ )
	for(int j = 1; j <= m; j ++ )
	if(g[i][j] == g[x][y])
	{
		if(i == x && j == y)
		continue;
		t.first = i, t.second = j;
		return t;
	}
}

int bfs()
{
	queue<PII> q; 
	int head = 0, tail = 0;
	q.push({Sx, Sy}), vis[Sx][Sy] = true;
	
	int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
	
	while(q.size())
	{
		PII t = q.front();
		q.pop();
		for(int i = 0; i < 4; i ++ )
		{
			int tx = t.first + dx[i], ty = t.second + dy[i];
			if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
			if(g[tx][ty] == '#' || vis[tx][ty]) continue;
			
			vis[tx][ty] = true, dist[tx][ty] = dist[t.first][t.second] + 1; 
			
			if(g[tx][ty] >= 'A' && g[tx][ty] <= 'Z')
			{
				PII T = _flash(tx, ty);
				q.push({T.first, T.second}), dist[T.first][T.second] = dist[tx][ty];
			}
			else q.push({tx, ty});		//**当到达传送门时，不能将传送门入队，因为如果将传送门入队，那么队列到达传送门的状态时 
		}								//会选择不走传送门的方法，而题目要求到达传送门必须使用，所以要判断来入队。 
	}
	return dist[Ex][Ey];
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ )
	for(int j = 1; j <= m; j ++ )
	{
		cin >> g[i][j];
		if(g[i][j] == '@')
		Sx = i, Sy = j;
		if(g[i][j] == '=')
		Ex = i, Ey = j;
	}
	cout << bfs() << endl;
}
/*
3 5
A#@A=
.#.#.
.....
*/