技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

深度优先搜索DFS与方格图的连通性判断

 收录于 蓝桥杯 算法Oj 算法
   约 2893 字   预计阅读 6 分钟 
https://bing.ee123.net/img/rand?artid=146298712

深度优先搜索（DFS）与方格图的连通性判断

在算法竞赛中， 方格图（Grid） 是常见的问题场景（如迷宫、岛屿问题等）。 DFS常用于遍历方格中的连通区域，判断连通性。

一、方格图的DFS核心思想

  1. 图的表示

    方格图通常用二维数组表示，每个格子可能有不同的状态（例如可通行或不可通行）。例如：

    • grid[i][j] = 0 表示水域（不可通行）
    • grid[i][j] = 1 表示陆地（可通行）

  2. 移动方向

    根据题目要求，每个格子可以向 4方向 （上下左右）或 8方向 （包括对角线）移动。需要定义方向数组：

    // 4方向：上、右、下、左
int dx4[] = {-1, 0, 1, 0};
int dy4[] = {0, 1, 0, -1};

// 8方向：包括对角线
int dx8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};

  3. DFS遍历步骤

    • 从起点出发，标记当前格子为已访问。
    • 遍历所有允许的方向，检查下一个格子是否在边界内、未被访问且可通行。
    • 递归访问所有连通区域。

二、C++代码实现

场景示例：统计方格图中的连通区域数量（如岛屿数量）

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

// 4方向移动数组
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};

// 8方向移动数组
const int dx8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};

// DFS遍历函数（4方向）
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
    int rows = grid.size();
    int cols = grid[0].size();
    
    visited[x][y] = true; // 标记当前格子已访问
    
    // 遍历4个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx4[i];
        int ny = y + dy4[i];
        // 检查边界、是否可访问、是否已访问
        if (nx >= 0 && nx < rows && ny >= 0 && ny < cols 
            && grid[nx][ny] == 1 && !visited[nx][ny]) {
            dfs(grid, visited, nx, ny);
        }
    }
}

// 统计连通区域数量
int countConnectedRegions(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;
    
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int count = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 发现未访问的陆地，启动DFS并计数
            if (grid[i][j] == 1 && !visited[i][j]) {
                dfs(grid, visited, i, j);
                count++;
            }
        }
    }
    return count;
}

int main() {
    // 示例输入：5x5的方格图
    vector<vector<int>> grid = {
        {1, 1, 0, 0, 0},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1}
    };
    
    cout << "连通区域数量（4方向）: " << countConnectedRegions(grid) << endl;
    return 0;
}

三、代码解析

  1. 方向数组

    • dx4 和 dy4 表示4个方向的坐标变化。
    • dx8 和 dy8 表示8个方向的坐标变化（可用于更复杂的连通性判断）。

  2. DFS函数

    • 递归访问当前格子的所有相邻可行走格子。
    • 通过 visited 数组避免重复访问。

  3. 统计连通区域

    • 遍历所有格子，对每个未访问的陆地启动一次DFS，统计启动次数即为连通区域数量。

四、扩展：8方向连通性

若允许8方向移动，只需修改方向数组和遍历循环：

// 修改DFS中的方向遍历
for (int i = 0; i < 8; i++) {
    int nx = x + dx8[i];
    int ny = y + dy8[i];
    // ... 其他逻辑不变
}

五、复杂度分析

  • 时间复杂度 ： O(rows × cols) ，每个格子被访问一次。
  • 空间复杂度 ： O(rows × cols) ，用于存储 visited 数组。

六、应用场景

  1. 岛屿问题（LeetCode 200）
  2. 迷宫寻路
  3. 图像中的连通区域分析

通过调整方向数组和状态判断逻辑，DFS可灵活应对各类方格图连通性问题。

七、 例题解析

问题描述

小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1 。


110010000011111110101001001001101010111011011011101001111110

010000000001010001101100000010010110001111100010101100011110 

001011101000100011111111111010000010010101010111001000010100 

101100001101011101101011011001000110111111010000000110110000 

010101100100010000111000100111100110001110111101010011001011 

010011011010011110111101111001001001010111110001101000100011 

101001011000110100001101011000000110110110100100110111101011 

101111000000101000111001100010110000100110001001000101011001 

001110111010001011110000001111100001010101001110011010101110 

001010101000110001011111001010111111100110000011011111101010 

011111100011001110100101001011110011000101011000100111001011 

011010001101011110011011111010111110010100101000110111010110 

001110000111100100101110001011101010001100010111110111011011 

111100001000001100010110101100111001001111100100110000001101 

001110010000000111011110000011000010101000111000000110101101 

100100011101011111001101001010011111110010111101000010000111 

110010100110101100001101111101010011000110101100000110001010 

110101101100001110000100010001001010100010110100100001000011 

100100000100001101010101001101000101101000000101111110001010 

101101011010101000111110110000110100000010011111111100110010 

101111000100000100011000010001011111001010010001010110001010 

001010001110101010000100010011101001010101101101010111100101 

001111110000101100010111111100000100101010000001011101100001 

101011110010000010010110000100001010011111100011011000110010 

011110010100011101100101111101000001011100001011010001110011 

000101000101000010010010110111000010101111001101100110011100 

100011100110011111000110011001111100001110110111001001000111 

111011000110001000110111011001011110010010010110101000011111 

011110011110110110011011001011010000100100101010110000010011 

010011110011100101010101111010001001001111101111101110011101

如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。

请问矩阵中最大的连通分块有多大？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M

算法代码：

# include <bits/stdc++.h>  // 包含标准库的所有头文件
using namespace std;  // 使用标准命名空间

// int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 定义四个方向的移动：上、右、下、左
// char g[100][100];  // 定义一个100x100的字符数组，用于存储矩阵
// int n = 30, m = 60;  // 定义矩阵的行数n为30，列数m为60

// int dfs(int x, int y) {  // 定义深度优先搜索函数，参数为当前坐标[x, y]
//     if (g[x][y] == '0') return 0;  // 如果当前点是'0'，返回0，表示不连通
//     g[x][y] = '0';  // 将当前点从'1'改为'0'，标记为已访问
//     int ans = 1;  // 初始化连通块的大小为1
//     for (int i = 0; i < 4; i++) {  // 遍历当前点的四个邻居
//         int nx = x + dx[i], ny = y + dy[i];  // 计算邻居的坐标
//         if (nx < 0 || ny < 0 || nx >= n || ny >= m)  // 如果邻居坐标超出边界
//             continue;  // 跳过该邻居
//         ans += dfs(nx, ny);  // 递归调用dfs，累加连通块的大小
//     }
//     return ans;  // 返回当前连通块的大小
// }

// int main() {
//     for (int i = 0; i < n; i++) cin >> g[i];  // 输入矩阵的每一行
//     int ans = 0;  // 初始化最大连通块的大小为0
//     for (int i = 0; i < n; i++)  // 遍历矩阵的每一行
//         for (int j = 0; j < m; j++)  // 遍历矩阵的每一列
//             if (g[i][j] == '1')  // 如果当前点是'1'
//                 ans = max(ans, dfs(i, j));  // 更新最大连通块的大小
//     cout << ans;  // 输出最大连通块的大小
//     return 0;  // 程序正常结束
// }

int main()
{
    cout<<"148";
    return 0;
}

先执行上面注释中的代码，输入测试数据（注意删除测试数据中间的空行），得到的答案后直接提交答案。因为测试数据挺多挺大的，使用DFS会超时是正常的，因为DFS使用到了递归（会占用到很大的栈空间，超过系统栈空间，会导致栈溢出），但是这是个填空题，直接搞出答案就可以了。

https://i-blog.csdnimg.cn/direct/20790ec15ba04e8a9ce1f14c53470bc4.png

2、

https://i-blog.csdnimg.cn/direct/1bf3b58714b24945863d0b8719ad509b.png

https://i-blog.csdnimg.cn/direct/6106244b1f894bbd8a88691251c62c72.png

算法代码：

#include <bits/stdc++.h>  // 包含标准库的所有头文件
using namespace std;  // 使用标准命名空间

int n, m;  // 定义矩阵的行数n和列数m
char Map[55][55];  // 定义一个55x55的字符数组，用于存储地图
int id[55][55], id_cnt = 0;  // id[x][y]表示点(x,y)属于第id_cnt个草地，id_cnt从1开始计数
vector<pair<int, int>> A[4];  // A[i]存储第i个草地中的所有点

int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};  // 定义四个方向的移动：下、右、上、左

void dfs(int x, int y, int c) {  // 深度优先搜索函数，参数为当前坐标[x, y]和草地编号c
    id[x][y] = c;  // 标记点(x,y)属于第c个草地
    A[c].push_back(make_pair(x, y));  // 将点(x,y)加入第c个草地的点集中
    for (int i = 0; i < 4; i++) {  // 遍历当前点的四个邻居
        int nx = x + dir[i][0], ny = y + dir[i][1];  // 计算邻居的坐标
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 如果邻居坐标超出边界，跳过
        if (Map[nx][ny] == '.') continue;  // 如果邻居是土地，跳过
        if (id[nx][ny]) continue;  // 如果邻居已经遍历过，跳过
        dfs(nx, ny, c);  // 递归调用dfs，继续搜索
    }
}

int Count(int x, int y, int i) {  // 计算点(x,y)到第i个草地的最短距离
    int ans = 100;  // 初始化最短距离为一个较大的值
    for (auto a : A[i])  // 遍历第i个草地的所有点
        ans = min(ans, abs(a.first - x) + abs(a.second - y));  // 计算曼哈顿距离并更新最小值
    return ans;  // 返回最短距离
}

int main() {
    cin >> n >> m;  // 输入矩阵的行数n和列数m
    for (int i = 0; i < n; i++) cin >> Map[i];  // 输入地图的每一行

    // 第1步：标记每个点属于哪个连通块
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (Map[i][j] == 'X' && !id[i][j])  // 如果当前点是草地且未被标记
                dfs(i, j, ++id_cnt);  // 进行DFS，标记连通块

    int ans = 100;  // 初始化答案为较大的值

    // 第2步：枚举每块土地，计算它到3个草地的最短距离
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (Map[i][j] == '.')  // 如果当前点是土地
                ans = min(ans, Count(i, j, 1) + Count(i, j, 2) + Count(i, j, 3) - 2);  // 计算到三个草地的最短距离并更新答案

    // 第3步：计算3个草地之间的最短距离
    int Min[4] = {0, 100, 100, 100};  // 初始化草地之间的最短距离
    for (int i = 1; i <= 3; i++) {  // 遍历每个草地
        int j = i + 1 <= 3 ? i + 1 : 1;  // 计算下一个草地的编号
        for (auto a : A[i])  // 遍历第i个草地的所有点
            Min[j] = min(Min[j], Count(a.first, a.second, j));  // 计算到下一个草地的最短距离并更新
    }

    // 第4步：计算连通3个草地的最短距离，并与情况(1)的结果比较
    for (int i = 1; i <= 3; i++)
        ans = min(ans, Min[i] + Min[i + 1 <= 3 ? i + 1 : 1] - 2);  // 计算连通三个草地的最短距离并更新答案

    cout << ans << endl;  // 输出最终答案
    return 0;  // 程序正常结束
}

https://i-blog.csdnimg.cn/direct/fe2d399b5a91475993fc3c21df14f70c.png

更新于 2025-03-16
 算法, 深度优先, C
返回 | 主页