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

洛谷1363题解法:虚拟坐标优化BFS解决循环迷宫问题(附代码详解)

2个月前 (06-30)

洛谷1363题解法:虚拟坐标优化BFS解决循环迷宫问题(附代码详解)  BFS算法 算法优化 C++代码 广度优先搜索 第1张

一、题目解读

洛谷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;
}

五、总结

本解法通过虚拟坐标巧妙解决循环迷宫的路径多样性问题,避免了传统BFS在循环结构中的冗余判断。核心在于利用相对位移记录路径方向,通过对比虚拟坐标快速确定是否存在多条有效路径,从而优化算法逻辑。该思路对处理类似循环问题具有通用性,是算法设计与优化的典型范例。


原创内容 转载请注明出处

分享给朋友:

相关文章

2022年蓝桥杯省赛B组扫雷(洛谷P8785)解题全解析:代码+思路+步骤详解

2022年蓝桥杯省赛B组扫雷(洛谷P8785)解题全解析:代码+思路+步骤详解

一、题目解读2022年蓝桥杯省赛B组机器人塔(洛谷P8785)是一道经典的算法题目,要求处理在一个二维平面上布置的炸雷与排雷火箭。炸雷具有爆炸半径,当排雷火箭引爆后,会触发周围范围内未被引爆的炸雷,形...

手搓二叉搜索树代码详解:从入门到实现(附完整注释)

一、简介和应用二叉搜索树(Binary Search Tree,BST)是一种经典的数据结构,其特点在于每个节点的左子树所有节点值均小于该节点,右子树所有节点值均大于该节点。这种特性使得它在查找、插入...

力扣2771题解析:双数组动态规划求解最长非递减子数组问题

力扣2771题解析:双数组动态规划求解最长非递减子数组问题

一、题目解读力扣2771题要求从两个整数数组nums1和nums2中合并元素,寻找最长非递减子数组的长度。非递减子数组指元素单调递增或相等的连续序列。题目难点在于需同时考虑两个数组的交互关系,找到全局...

NOI 2001密码锁(洛谷P2024)解题全解析:并查集+关系标记算法实战

NOI 2001密码锁(洛谷P2024)解题全解析:并查集+关系标记算法实战

一、题目解读2001年NOI密码锁(洛谷P2024)是一个经典的逻辑判断问题。题目描述了一个动物园中动物之间的关系,需要处理两种类型的陈述:同类关系(1)和捕食关系(2)。要求根据给定的K条关系,判断...

LeetCode 2523题解:寻找区间内最小间隔质数对(C++代码)

LeetCode 2523题解:寻找区间内最小间隔质数对(C++代码)

一、题目解读LeetCode 2523题要求在一个给定的整数区间 [left, right] 内,找到间隔最小的两个质数(即相邻质数的差值最小),并返回这对质数。若区间内不存在两个质数,则返回 [-1...

牛客13279题解:基于广度优先搜索(BFS)计算树高度的算法优化与代码实现

牛客13279题解:基于广度优先搜索(BFS)计算树高度的算法优化与代码实现

一、题目解读牛客13279题要求计算给定树的高度。树由n个节点组成,通过n-1条边连接,形成一棵有根树。题目核心在于高效求解树的高度,即从根节点到最深叶子节点的最长路径长度。需要理解树的结构特点,选择...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。