leetcode200：岛屿数量

题目链接

leetcode

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

C++ 代码

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

/*
    深度优先搜索
    
    将二维网格看成一个无向图，垂直或水平相邻的 1 之间有边相连。
    为了求出岛屿的数量，搜索整个二维网格。
    如果一个位置为 1，则以它为起始节点进行深度优先搜索。
    在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
    最终岛屿的数量，即为深度优先搜索的次数。

    时间复杂度：O(mn)
        其中 m 和 n 分别为行数和列数。
    空间复杂度：O(mn)
        在最坏情况下，整个网格都是 1，深度优先搜索的深度达到 mn。
*/
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int res = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }

        return res;
    }

    void dfs(vector<vector<char>>& grid, int x, int y) {
        grid[x][y] = '0';
        for (int i = 0; i < 4; i++) {
            int new_x = x + dx[i], new_y = y + dy[i];
            if (new_x >= 0 && new_x < grid.size() && new_y >= 0 && new_y < grid[0].size() && grid[new_x][new_y] == '1') {
                dfs(grid, new_x, new_y);
            }
        }
    }

private:
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
};

/*    
    广度优先搜索

    将二维网格看成一个无向图，垂直或水平相邻的 1 之间有边相连。
    为了求出岛屿的数量，搜索整个二维网格。
    若一个位置为 1，则将它加入队列，开始进行广度优先搜索。
    在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
    直到队列为空，搜索结束。
    最终岛屿的数量，即为广度优先搜索的次数。

    时间复杂度：O(mn)
        其中 m 和 n 分别为行数和列数。
    空间复杂度：O(min(m,n))
        在最坏情况下，整个网格都是 1，队列的大小可以达到 min(m,n)。
*/
class Solution_1 {
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        int res = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    bfs(grid, i, j);
                }
            }
        }

        return res;
    }

    void bfs(vector<vector<char>>& grid, int x, int y) {
        int rows = grid.size(), cols = grid[0].size();
        queue<int> q;
        q.push(x*cols + y);
        grid[x][y] = '0';

        while (!q.empty()) {
            int cur = q.front(); q.pop();
            int cur_x = cur / cols, cur_y = cur % cols;
            for (int i = 0; i < 4; i++) {
                int new_x = cur_x + dx[i], new_y = cur_y + dy[i];
                if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && grid[new_x][new_y] == '1') {
                    q.push(new_x* cols + new_y);
                    grid[new_x][new_y] = '0';
                }
            }
        }
    }

private:
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<char>>& nums) {
    cout << "[\n";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << "\"" << nums[i][j] << "\"";
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
        cout << "\n";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<vector<char>>> grid_cases = {
        {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        },
        {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        },
    };

    for (int i = 0; i < grid_cases.size(); i++) {
        auto& grid = grid_cases[i];
        cout << "Input: grid = ";
        printArray(grid);

        // 计算岛屿数量
        int result = solution.numIslands(grid);
        cout << "Output: " << result << endl;
        cout << "----------------" << endl;
    }

    return 0;
}