当前位置：首页 > 洛谷 > 洛谷1363题解法：虚拟坐标优化BFS解决循环迷宫问题（附代码详解）

洛谷1363题解法：虚拟坐标优化BFS解决循环迷宫问题（附代码详解）

3天前

一、题目解读

洛谷1363题要求判断在给定大小的循环迷宫中，从起点出发是否可以通过移动到达多个不同的路径方向。迷宫由字符矩阵表示，'S'为起点，'#'为障碍物，其余为可通行区域。由于迷宫存在循环（即超出边界后从另一侧重新进入），需判断是否存在多条有效路径，避免陷入无限循环。

二、解题思路

核心思路为广度优先搜索（BFS）结合虚拟坐标。普通BFS无法处理循环迷宫中的路径重复问题，因此引入虚拟坐标（virtX, virtY）记录每个位置的“相对位移”。每当到达新节点时，若其虚拟坐标与已访问节点不同，说明存在多条路径，即可判定可逃脱。

三、解题步骤

1. 初始化：读取迷宫矩阵，定位起点(startX, startY)，初始化队列和访问标记。

2. BFS遍历：从起点开始，依次遍历上、下、左、右四个方向。

3. 边界处理：使用取模运算实现循环边界（如nx = (x + dx + n) % n），确保坐标合法。

4. 虚拟坐标更新：每次移动时，虚拟坐标根据相对位移计算（vx = virtX[x][y] + dx）。

5. 关键判断：若新节点未被访问，标记并加入队列；若已被访问且虚拟坐标不同，直接返回True（可逃脱）。

6. 终止条件：队列为空时仍未找到不同路径，则返回False。

四、代码与注释

#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;
    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;
}