洛谷：P1825：Corn Maze S

题目

P1825：Corn Maze S

作为BFS、DFS在书中对应章节习题的最后一个，我就放上来了。

分析

###=##
#.W.##
#.####
#.@W##
######

先看图例，如果我们不考虑滑梯（图中的两个W），那么这是一个直接了当的迷宫题目，用BFS就可以了，基本框架、走通条件都是很常规的。

    while (!q.empty())
    {
        Point current = q.front();                    // 获取当前处理的位置
        q.pop();

        // 如果到达出口，输出时间并结束
        if (current.x == exit.x && current.y == exit.y)
        {
            cout << current.time << endl;
            return 0;
        }

        // 尝试向四个方向移动
        for (auto& dir : directions)
        {
            int nx = current.x + dir[0];              // 计算新位置的坐标
            int ny = current.y + dir[1];

            // 检查新位置是否有效（在地图范围内且不是墙）
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#')
            {
                int new_time = current.time + 1;      // 移动到新位置需要1单位时间

                // 如果新位置是滑梯端点，立即传送到另一端
                if (isupper(maze[nx][ny]))
                {
                    // ...
                }
                // 如果新位置是普通草地或出口
                else if (dist[nx][ny] == -1 || dist[nx][ny] > new_time)
                {
                    // ...
                    // 更新到达该位置的最短时间
                    q.push({nx, ny, new_time});       // 将新位置加入队列
                }
            }
        }
    }

我们先不考虑新位置是否是滑梯，那么只要写q.push(...)就好了。

考虑滑梯

滑梯一定是成对出现的，所以我们要记录：

• 滑梯的编号：一个大写字母
• 滑梯的坐标：一个点坐标。

程序中用一个unordered_map<char, vector<pair<int, int>>>来表示：

• char：代表滑梯的编号
• pair<int, int>表示坐标
• vector<pair<...>>表示成对关系：滑梯总是成对出现

考虑滑梯后，所谓的下一个点就有了新的变化，也就是说，如果BFS搜索的“下一个位置”是滑梯，就要瞬时传递到滑梯的另一头。

                int new_time = current.time + 1;      // 移动到新位置需要1单位时间

                // 如果新位置是滑梯端点，立即传送到另一端
                if (isupper(maze[nx][ny]))
                {
                    char slideChar = maze[nx][ny];    // 获取滑梯字母
                    for (auto& endpoint : slides[slideChar]) // 遍历该滑梯的所有端点
                    {
                        // 找到不是当前端点的另一个端点
                        if (endpoint.first != nx || endpoint.second != ny)
                        {
                            // 如果另一端点未访问过或找到更短路径，则更新
                            if (dist[endpoint.first][endpoint.second] == -1 || 
                                dist[endpoint.first][endpoint.second] > new_time)
                            {
                                dist[endpoint.first][endpoint.second] = new_time;
                                q.push({endpoint.first, endpoint.second, new_time});
                            }
                            break; // 只传送到另一端，不需要继续遍历
                        }
                    }
                }

有鉴于此，对于常规的移动，我们也要加一个判断：因为到达任何一个常规点可以是从一个常规点过来，或者是从滑梯过来。

完整代码如下。

答案

思考

就用这道题，作为BFS和DFS的结束吧！