P1825 [USACO11OPEN]Corn Maze S

The question ：

Cows go to a  N\times MN×M  Corn maze ,2 \leq N \leq 300,2 \leq M \leq3002≤N≤300,2≤M≤300.

There are some conveyors in the maze , You can transfer cows from one point to another in an instant . These devices can be used in both directions .

If a cow is at the beginning or end of the device , This cow is must Use this device .

Corn maze is surrounded by corn except for the only exit .

Each element in the maze consists of one of the following items ：

1. corn ,#  Express , These grids are not passable .
2. The grass ,.  Express , It can be easily passed .
3. Conveyor , Each pair of capital letters  \tt{A}A  To  \tt{Z}Z  Express .
4. exit ,=  Express .
5. The starting point , @  Express

Cows can move in four adjacent grids that may exist on a grid of grass , cost  11  Unit time . It doesn't take time to go from one node of the device to another .

Input ：

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

Output ：

3

Ideas ： According to the meaning of the topic, you can use bfs solve , Special attention should be paid to the special handling when arriving at the transfer point , There is no need to mark between transfer points , Because the transfer point may need to be used many times . Examples ：

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

  The way to go at this time is 1,3 ->1,4->1,1->2,1->1,1->1,4->1,5. Because transmission does not take time , So a total of 4 Unit time , At this time, the portal is reused twice . So the portal doesn't need to be marked . So how to place it between the portals to lead the lethal cycle back and forth ？ There is no need to worry about this problem , Because I arrived at the portal , Then I will mark the point around the portal as true. And then my dx and dy Arrays only go up, down, left and right 4 The state of two directions , There is no direct transmission state . So there will be no direct transmission between portals , Instead, you need to go out of the portal and then enter the portal to transmit , So there will be no dead cycle .

Then we can be happy AC 了 ,code as follows ：

#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});		//** When you reach the portal , The portal cannot be queued , Because if you join the portal , When the queue reaches the state of the portal  
		}								// Will choose not to go through the portal , The title requires that you must use , So judge to join the team . 
	}
	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=
.#.#.
.....
*/