【题目链接】
洛谷 P1825 [USACO11OPEN]Corn Maze S
【题目考点】
1. 广搜 迷宫问题
【解题思路】
输入地图，记录起点、终点。
设方向数组dir，方便取一个格子上下左右的位置。
从起点出发进行广搜，把位置及到该位置的步数打包成一个结点，队列中保存这样的结点。每出队一个结点，访问该结点位置上下左右的四个位置，该位置必须同时满足条件：在地图内、未访问过、不是墙。如果满足条件，则访问该位置，到该位置的步数加1，把该位置和步数打包成结点入队。
本题难点在于处理传送门。
我这里的处理方法是：设tempGate数组，数组的每个元素是一个vector，方便添加数据。vector中的元素类型是数对pair<int, int>，表示一个传送门的位置。tempGate[i]这个vector中保存的是字母为i+'A'的传送门的两个位置。
而后设数对到数对的映射gate，声明方法为：map<pair<int,int>,pair<int,int>> gate;，目的是方便通过传送门A的位置得到传送门B的位置。
遍历tempGate数组，把每个vector中的两个元素之间建立映射关系即可。一个传送门位置作为键， 另一个传送门位置作为值。
在广搜时，如果从当前位置出发走一步到达的位置是传送门，则正常进行，将该位置标记为已访问，打包该位置和步数成一个结点，结点入队。
当出队的位置是传送门时，让牛从当前所在传送门的位置传送到另一个门的位置，从这里开始继续走。
注意这时并不算访问了传送门的出口。
比如走到了传送门
A
1
A_1
A1，访问了
A
1
A_1
A1，等到
A
1
A_1
A1位置出队时，直接跳到另一个传送门位置
A
2
A_2
A2，接着从
A
2
A_2
A2出发继续走，但并没有访问
A
2
A_2
A2。
因为也还可能存在路径先走到
A
2
A_2
A2，然后传送到
A
1
A_1
A1，这条路还是应该可以走的。
【题解代码】
解法1：广搜
- 写法1：使用STL
#include <bits/stdc++.h>
using namespace std;
#define N 305
struct Node
{
int x, y, s;
Node(){}
Node(int a, int b, int c = 0):x(a), y(b), s(c){}//第三项步数如不填，则默认为0
};
int n, m, sx, sy, ex, ey;
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
char mp[N][N];
vector<pair<int, int>> tempGate[26];//tempGate[i]:传送门i+'A'的两个位置
map<pair<int, int>, pair<int, int>> gate;//gate[i]：传送门i对应的位置
bool vis[N][N];
int bfs()//返回走出迷宫的最少步数
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy, 0));
while(que.empty() == false)
{
Node u = que.front();
que.pop();
if(u.x == ex && u.y == ey)//走出迷宫
return u.s;
if(isupper(mp[u.x][u.y]))//如果u位置是传送门，则通过传送门
{
pair<int, int> t = gate[make_pair(u.x, u.y)];
u.x = t.first, u.y = t.second;
}
for(int i = 0; i < 4; ++i)
{
int x = u.x+dir[i][0], y = u.y+dir[i][1];
if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
que.push(Node(x, y, u.s+1));
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
sx = i, sy = j;//起点
else if(mp[i][j] == '=')
ex = i, ey = j;//终点
else if(isupper(mp[i][j]))//如果是大写字母
tempGate[mp[i][j]-'A'].push_back(make_pair(i, j));
}
for(int i = 0; i < 26; ++i)//构建映射gate
{
if(tempGate[i].size() > 0)//同一种传送门只能存在两个
{
gate[tempGate[i][0]] = tempGate[i][1];//一个传送门位置作为键， 另一个传送门位置作为值
gate[tempGate[i][1]] = tempGate[i][0];
}
}
cout << bfs();
return 0;
}
- 写法2：C风格
#include <iostream>
using namespace std;
#define N 305
struct Pair
{
int x, y;
};
int n, m, sx, sy, ex, ey;
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
char mp[N][N];
int step[N][N];//step[i][j]:到(i, j)的步数
Pair tempGate[26][2];//tempGate[i]:传送门i+'A'的两个位置
int tgn[26];//tgn[i]：传送门i+'A'已经出现的个数
bool vis[N][N];
Pair getAnotherGate(Pair p)//已知传送门在p位置，求传送门的另一个传送门的位置
{
int ind = mp[p.x][p.y]-'A';
if(p.x == tempGate[ind][0].x && p.y == tempGate[ind][0].y)
return tempGate[ind][1];
else
return tempGate[ind][0];
}
int bfs()//返回走出迷宫的最少步数
{
Pair que[N*N];
int head = 0, tail = 0;//队列
vis[sx][sy] = true;//还应该有step[sx][sy] = 0;全局变量默认为0，就不写了。
++tail;
que[tail].x = sx, que[tail].y = sy;//(sx, sy)入队
while(head != tail)
{
Pair u = que[++head];//出队
if(u.x == ex && u.y == ey)//走出迷宫
return step[u.x][u.y];
if(mp[u.x][u.y] >= 'A' && mp[u.x][u.y] <= 'Z')//如果u位置是传送门，则通过传送门
{
int st = step[u.x][u.y];//把到传送门起点的步数转移到终点
u = getAnotherGate(u);
step[u.x][u.y] = st;
}
for(int i = 0; i < 4; ++i)
{
int x = u.x+dir[i][0], y = u.y+dir[i][1];
if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
step[x][y] = step[u.x][u.y]+1;
++tail;
que[tail].x = x, que[tail].y = y;
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
sx = i, sy = j;//起点
else if(mp[i][j] == '=')
ex = i, ey = j;//终点
else if(mp[i][j] >= 'A' && mp[i][j] <= 'Z')//如果是大写字母
{
int ind = mp[i][j]-'A';
tempGate[ind][tgn[ind]].x = i, tempGate[ind][tgn[ind]].y = j;
tgn[ind]++;
}
}
cout << bfs();
return 0;
}
