代码随想录训练营第56天|广度优先搜索-100. 岛屿的最大面积

// 版本二
#include <iostream>
#include <vector>
using namespace std;

int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, int x, int y) {
    grid[x][y] = 0; // 标记访问过
    count++;
    for (int i = 0; i < 4; i++) {
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        if (nextx >= 0 && nextx < grid.size() && nexty >= 0 && nexty < grid[0].size() && grid[nextx][nexty] == 1){
            dfs(grid, nextx, nexty);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                count = 0; // 因为dfs处理当前节点,所以遇到陆地计数为0,进dfs之后在开始从1计数
                dfs(grid, i, j); // 将与其链接的陆地都标记上 true
                result = max(result, count);
            }
        }
    }
    cout << result << endl;
}

深搜,用全局变量累计单个岛屿面积。主程序里用result选出最大。

上一篇:卡尔曼滤波推导过程|MATLAB滤波|MATLAB卡尔曼|MATLAB卡尔曼导航


下一篇:LeetCode讲解篇之695. 岛屿的最大面积-题解代码