当前位置：首页 > 洛谷 > 洛谷P1141题解：迷宫连通块问题的深度优先搜索算法与代码解析

洛谷P1141题解：迷宫连通块问题的深度优先搜索算法与代码解析

2天前

一、题目解读

洛谷P1141题目要求处理一个由字符构成的迷宫，其中相同字符形成连通块，不同字符构成分隔。题目需统计连通块数量及大小，并支持查询两点是否属于同一连通块。核心在于高效识别并标记迷宫中的连通区域，同时处理边界条件和查询操作。

二、解题思路

采用**深度优先搜索（DFS）**策略。首先遍历迷宫，遇到未标记的单元格时启动DFS，将相邻的不同字符单元格合并为同一连通块，并记录块大小。通过方向数组实现四向遍历，利用队列优化搜索过程，确保遍历所有可达区域。最终通过连通块标记数组判断查询点的归属。

三、解题步骤

1. 输入处理：读取迷宫尺寸n×m，外层包裹边界防止越界访问，按行列顺序存储字符。

2. 连通块标记：初始化标记数组为零。遍历每个单元格，若未标记则启动DFS：

入队当前坐标，标记为当前连通块编号，计数初始化。

循环队列：取出队头坐标，遍历四向邻点。

若邻点满足边界、未标记且字符不同，则合并至当前块（标记编号、计数+1、入队）。

3. 查询处理：循环m次，读取查询坐标，直接比较标记数组值判断连通性。

四、代码与注释

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 方向数组：上、下、左、右
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加快输入输出速度
    
    int n, m;
    cin >> n >> m; // 迷宫尺寸n×m，查询次数m
    
    // 读取迷宫，注意题目行列从1开始
    vector<vector<char>> grid(n+2, vector<char>(n+2));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> grid[i][j];
        }
    }
    
    // 连通块标记和大小统计
    vector<vector<int>> component(n+2, vector<int>(n+2, 0));
    vector<int> component_size(1); // 从1开始计数
    
    int current_component = 0; // 当前连通块编号
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (component[i][j] == 0) { // 未标记单元格
                current_component++; // 创建新连通块
                queue<pair<int, int>> q; // 队列辅助DFS
                q.push({i, j}); // 起始坐标入队
                component[i][j] = current_component; // 标记
                int size = 1; // 块大小初始化
                
                while (!q.empty()) { // 遍历可达区域
                    auto [x, y] = q.front(); // 取出队头坐标
                    q.pop();
                    
                    for (int k = 0; k < 4; ++k) { // 四向扩展
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        
                        // 检查边界、未访问且数字相反
                        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n &&
                            component[nx][ny] == 0 && 
                            grid[nx][ny]!= grid[x][y]) {
                            component[nx][ny] = current_component; // 合并标记
                            size++; // 统计块大小
                            q.push({nx, ny}); // 邻点入队
                        }
                    }
                }
                component_size.push_back(size); // 记录块大小
            }
        }
    }
    
   
// 处理查询
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << component_size[component[x][y]] << "\n";
    }
}