P1825 题解【有具体的思路分析过程】

· · 个人记录

题目分析：

很明显地，这道题是一道走迷宫的问题。与其他的迷宫题相比，此题最大的亮点就是带有科技感的“传送门”：走到一个传送门就会被传送到另一个对应的门。其他的和其他的迷宫题一样，我们要求的是从起点走到终点的最短步数。BFS搜索就可以解决了。

思路分析：

在BFS之前我们需要处理：1.存下这个图；2.找到起点；3.储存好每对传送门的位置。

当然在看分析之前可以先移到下面看一下完整的代码，先有一个整体了解。

1.存图：

我们可以用 char 数组存图。因为此题中有传送门，所以我们不需要也不好另开 bool 数组处理哪些点可走、哪些点不可走。我们通过字符来判断就行。

2.找起点：

BFS需要有搜索起点。但由于题目没有直接给出起点，所以我们需要遍历地图找到起点，而终点我们是不需要找的，因为此题我们BFS结束的判断条件即为找到终点，搜索过程中字符判断就行了。

3.储存传送门位置：

由于此题的传送门的对数是有限的，而且是用字符 A - Z 来表示每对传送门的，所以我们完全可以将每对传送门的位置存下来。当然啊，你也可以选择不储存传送门的位置，用遍历地图方式来查找传送门的位置。按照自己的喜好选择。但是我介绍的是储存传送门位置的方法。

储存：
//pre: 在BFS之前进行处理
//a[][]:字符地图
//sx, sy:起点的坐标
//strans:传送（stransmit）
 stans[30][2][2]
 第一维表示不同的传送门
 第二维表示一对传送门
 第三维表示一个传送门的位置
//idx[30]:表示每对传送门已经有几个进来了。
//下面的所有代码中数组的储存都是从下标0开始的。
void pre() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char ch = a[i][j];
            if (ch == '@') {sx = i, sy = j;}
            if (ch >= 'A' && ch <= 'Z') {
                strans[ch-'A'][idx[ch-'A']][0] = i;
                strans[ch-'A'][idx[ch-'A']][1] = j;
                idx[ch-'A']++;
            }
        }
}

预先的步骤处理完之后我们就可以开始搜索了

BFS 搜索：

1.位置状态：

存位置状态的话我是使用结构体 + stl队列的。

struct node {
    int x, y, step;
};
queue<node> q;

当然你们也可以使用二维的数组来代替。

2.方向：
int fx[4] = {-1, 1, 0, 0};
int fy[4] = {0, 0, 1, -1};
3.到此一游的标记：

走过的点我们就不需要继续走了。

bool st[N][N];
4.位置转移：
int bfs() {
    queue<node> q;
    q.push({sx, sy, 0}); //起始位置入队
    st[sx][sy] = true;//到此一游标记
    while (q.size()) {
        node t = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int x = t.x + fx[i], y = t.y + fy[i];
            if (!check(x, y)) continue; //判断该点能不能走，check函数代码放在下面了。
            else if (a[x][y] == '=') return t.step + 1; //走到终点，直接返回了。
            else if (a[x][y] == '.') {q.push({x, y, t.step + 1}); st[x][y] = true;}//该点可走，入队
            else { // 传送门
                get_strans(x, y); // 遇到传送门的地方我们直接向另一个传送门转移。因为题目就是这样说的。函数代码放在下面了。
                q.push({x, y, t.step + 1});传送门不能标记到此一游的标记。这也是本题十分值得思考的地方。
            }
        }
    }
}

check函数：

bool check(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || a[x][y] == '#' || st[x][y]) return false;
    //越界、遍历过、墙 都是不走的
    return true;
}

get_strans函数：

void get_strans(int &x, int &y) {
    int j = 0;
    char ch = a[x][y];
    while (strans[ch-'A'][j][0] == x && strans[ch-'A'][j][1] == y) j++;//找到另一个点，当然这里的 while 改成 if 也是的可以的，看个人习惯。
    x = strans[ch-'A'][j][0], y = strans[ch-'A'][j][1];//直接被传送走了
}

AC代码：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 310;
struct node {
    int x, y, step;
};
int n, m;
int sx, sy, strans[30][2][2], idx[30];
int fx[4] = {-1, 1, 0, 0}, fy[4] = {0, 0, 1, -1};
char a[N][N];
bool st[N][N];
void pre() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char ch = a[i][j];
            if (ch == '@') {sx = i, sy = j;}
            if (ch >= 'A' && ch <= 'Z') {
                strans[ch-'A'][idx[ch-'A']][0] = i;
                strans[ch-'A'][idx[ch-'A']][1] = j;
                idx[ch-'A']++;
            }
        }
}
bool check(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || a[x][y] == '#' || st[x][y]) return false;
    return true;
}
void get_strans(int &x, int &y) {
    int j = 0;
    char ch = a[x][y];
    while (strans[ch-'A'][j][0] == x && strans[ch-'A'][j][1] == y) j++;
    x = strans[ch-'A'][j][0], y = strans[ch-'A'][j][1];
}
int bfs() {
    queue<node> q;
    q.push({sx, sy, 0});
    st[sx][sy] = true;
    while (q.size()) {
        node t = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int x = t.x + fx[i], y = t.y + fy[i];
            if (!check(x, y)) continue;
            else if (a[x][y] == '=') return t.step + 1;
            else if (a[x][y] == '.') {q.push({x, y, t.step + 1}); st[x][y] = true;}
            else {
                get_strans(x, y);
                q.push({x, y, t.step + 1});
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", a[i]);
    pre();
    printf("%d\n", bfs());
    return 0;
}

最后再解答一下为什么传送门不能标记的问题

其实就是为了解决传送门堵路的问题

给个样例就能懂了：

##########
###.=.####
###...####
##......##
####A#####
##......##
##.....###
##@#######
####..A..#
##########

好的，这篇题解到这里就结束了，祝大家越来越强！