BFS算法实战：洛谷P1363迷宫逃脱问题的虚拟坐标解法

一、问题描述与解题思路

洛谷P1363题目要求我们判断在一个可以无限延伸的迷宫中，玩家是否能从起点出发永远逃脱。迷宫具有周期性重复的特点，传统的BFS算法无法直接应用，需要引入虚拟坐标的概念来解决这个特殊问题。

二、完整代码实现（带详细注释）

#include <iostream>
#include <queue>
#include <cstring>
using namespACe std;

const int N = 1505;  // 定义迷宫最大尺寸
char grid[N][N];     // 存储迷宫地图
bool vis[N][N];      // 记录访问状态
int virtX[N][N], virtY[N][N];  // 存储虚拟坐标
int n, m, startX, startY;      // 迷宫尺寸和起点坐标
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};  // 四个移动方向

bool canEscape() {
    queue<pair<int,int>> q;  // BFS队列
    q.push({startX, startY});
    vis[startX][startY] = true;
    virtX[startX][startY] = startX;  // 初始化虚拟坐标
    virtY[startX][startY] = startY;

    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        
        for (auto [dx,dy] : dirs) {
            int nx = (x + dx + n) % n;  // 处理周期性边界
            int ny = (y + dy + m) % m;
            int vx = virtX[x][y] + dx;  // 计算新虚拟坐标
            int vy = virtY[x][y] + dy;

            if (grid[nx][ny] == '#') continue;  // 遇到墙则跳过

            if (!vis[nx][ny]) {  // 未访问过的位置
                vis[nx][ny] = true;
                virtX[nx][ny] = vx;
                virtY[nx][ny] = vy;
                q.push({nx, ny});
            } 
            else if (virtX[nx][ny] != vx || virtY[nx][ny] != vy) {
                return true;  // 发现不同虚拟坐标，说明可以逃脱
            }
        }
    }
    return false;  // 无法逃脱
}

int main() {
    while (cin >> n >> m) {  // 处理多组输入
        memset(vis, 0, sizeof(vis));  // 初始化访问数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> grid[i][j];
                if (grid[i][j] == 'S') {  // 记录起点位置
                    startX = i; startY = j;
                }
            }
        }
        cout << (canEscape() ? "Yes" : "No") << endl;  // 输出结果
    }
    return 0;
}

三、算法核心解析

1. 虚拟坐标系统：

• 真实坐标(nx,ny)通过模运算处理周期性边界

• 虚拟坐标(vx,vy)记录实际移动距离，不受迷宫尺寸限制

2. BFS搜索过程：

• 从起点开始广度优先搜索

• 每次移动计算真实坐标和虚拟坐标

• 遇到已访问节点时比较虚拟坐标，若不同则说明可以逃脱

3. 逃脱条件判断：

• 当移动到同一真实坐标但虚拟坐标不同时

• 说明可以通过不同路径到达"相同"位置，即迷宫可以无限延伸

四、复杂度分析与优化建议

1. 时间复杂度：

• 标准的BFS复杂度：O(n×m)

• 每个网格节点最多被访问一次

2. 空间复杂度：

• 需要存储迷宫地图和访问状态

• 额外需要存储虚拟坐标信息

3. 优化建议：

• 可以使用位运算压缩存储空间

• 对于特别大的迷宫，可以考虑分块处理