题目扩展
题目描述
奶牛们去一个 N×M 玉米迷宫，2≤N≤300,2≤M≤300。迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。
这些装置可以双向使用。
如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置，奶牛在传送过后不会立刻进行第二次传送，即不会卡在传送装置的起点和终点之间来回传送。
玉米迷宫除了唯一的一个出口都被玉米包围。
迷宫中的每个元素都由以下项目中的一项组成：
玉米，# 表示，这些格子是不可以通过的。
草地，. 表示，可以简单的通过。
传送装置，每一对大写字母 A 到 Z 表示。
出口，= 表示。
起点， @ 表示
奶牛能在一格草地上可能存在的四个相邻的格子移动，花费1个单位时间。从装置的一个结点到另一个结点不花时间。
样例
输入
5 6
###=##
#.W.##
#.####
#.@W##
######
输出
3
题目分析
本题的难点在于加入了一个新的元素：传送门。
根据题目描述，传送门的特点有：
1.一旦是通过dx,dy移动到传送门（设为A1），那么必须就要传送到对应的另一个传送门（设为A2）的位置，其余情况下到达传送门A2时一定不能发生传送（即从传送门A1传送过来到达的A2）
2.传送门可能不成对，此时的传送门相当于普通点’.’
如此以来，由传送门的特点引发了这一“特殊情况”：当从A1传送到A2之后，我们可以从A2随便向四周走一步再回到A2，然后再触发传送条件传送到A1，如下图所示，当我们从（4，3）传送到（2，4）时，我们可以（2，4）–>（2，5）–>（2，4），然后再传送到（4，3）。
123456
1 ######
2 ###A.#
3 ######
4 #A@###
5 #=####
因此我们需要在广搜中（在进行dx和dy位移之前）多增加一个特判：当前是否为传送门（设为A1），是的话，我们就需要找到另一个传送门（设为A2）所在坐标，然后将传送门A1的坐标替换成传送门A2所在点的坐标，然后利用A2的坐标进行dx和dy的位移操作；如果不是的话，那么依然使用A1的坐标进行dx和dy的位移操作。这也意味着在进行st数组标记某个点最短距离是否确定时，只有通过dx和dy位移走到的点才能进行标记，比如在(1,2)–>A1–>A2–>(5,6)–>(5,5)中，点A1,(5,6),(5,5)都需要标记st=true，但A2不能被标记st=true，并且当A2再传送到A1的时候依然可以传送，这是因为传送时不需要进行st的判定，只有dx和dy位移时才进行st的判定（只有st==false才能进行位移操作）。综上所述，这些操作可以在保证bfs基本操作的同时（位移操作），又保证了上述所说的“特殊情况”。
有一点需要注意的是，在本题中我们不单设一个最短距离数组dist[]来记录每个点的最短距离，而是将最短距离和点的坐标一起保存在bfs队列中，这是因为由于传送门的存在导致会出现传送门堵住出口的情况：
123456
1###=##
2#..W.#
3#....#
4##@..#
5#....#
6#....#
7#..W.#
8######
如上图所示，W(2,4)距离起点的最短距离应该是3，但因为它堵住了出口，所以它的最短距离对于起终最短距离来说不起丝毫作用，最终W(2,4)应该使用的是从W(7,4)传送过来的最短距离，即利用W(7,4)的最短距离计算起终最短距离，而不是利用W(2,4)本身的最短距离，前者用“最短距离和点的坐标一起保存在bfs队列中”的方法即可简单实现，而使用特设最短距离数组dist只能在本题中简单实现“各个点本身的最短距离”，想实现前者可能会很困难（因为dist[]记录的是每个点的最短距离），相关代码见“Wrong Code”。（Wrong Code在洛谷中只卡在了上图样例当中）
AC Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
bool st[N][N];
char g[N][N];
int n, m;
int ex, ey;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
struct point{
int x, y, d;
};
queue<point> q;
void get_exit(int &x0, int &y0)
{
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
if(g[i][j] == g[x0][y0] && (i != x0 || j != y0))
{
x0 = i, y0 = j;
return;
}
}
}
int bfs()
{
while(q.size())
{
auto t = q.front();
q.pop();
int x0 = t.x, y0 = t.y, dist = t.d;
//cout << x0 << " " << y0 << " " << dist << endl;
if(g[x0][y0] >= 'A' && g[x0][y0] <= 'Z')
{
get_exit(x0, y0);
//cout << endl << x0 << " " << y0 << endl << endl;
}
for(int i = 0; i < 4; i ++)
{
int x = x0 + dx[i], y = y0 + dy[i];
if(g[x][y] == '#' || st[x][y] == 1 || x < 1 || y < 1 || x > n || y > m) continue;
st[x][y] = 1;
q.push({x, y, dist + 1});
if(g[x][y] == '=') return dist + 1;
}
}
return -1;
}
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] == '@')
{
q.push({i, j, 0});
st[i][j] = 1;
}
}
}
int t = bfs();
cout << t << endl;
return 0;
}
Wrong Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
queue<PII> q;
bool st[N][N];
int d[N][N];
char g[N][N];
int n, m;
int ex, ey;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
void get_exit(int &x0, int &y0)
{
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
if(g[i][j] == g[x0][y0] && (i != x0 || j != y0))
{
/*if(st[i][j] == 0 || d[i][j] > d[x0][y0])*/ d[i][j] = d[x0][y0];
x0 = i, y0 = j;
return;
}
}
}
int bfs()
{
while(q.size())
{
auto t = q.front();
q.pop();
int x0 = t.first, y0 = t.second;
//cout << x0 << " " << y0 << " " << d[x0][y0] << endl;
if(g[x0][y0] >= 'A' && g[x0][y0] <= 'Z')
{
get_exit(x0, y0);
//cout << endl << x0 << " " << y0 << endl << endl;
}
for(int i = 0; i < 4; i ++)
{
int x = x0 + dx[i], y = y0 + dy[i];
if(g[x][y] == '#' || st[x][y] == 1 || x < 1 || y < 1 || x > n || y > m) continue;
st[x][y] = 1;
d[x][y] = d[x0][y0] + 1;
q.push({x, y});
if(g[x][y] == '=') return d[x][y];
}
}
return -1;
}
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] == '@')
{
q.push({i, j});
d[i][j] = 0;
st[i][j] = 1;
}
}
}
int t = bfs();
cout << t << endl;
return 0;
}
