leetcode200：岛屿数量

题目链接

leetcode

题目描述

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

C++ 代码

// 200. 岛屿数量
// 高频面试题 - CodeTop

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

void printGrid(vector<vector<char>>& grid) {
    for (int i = 0; i < grid.size(); i ++) {
        for (int j = 0; j < grid[0].size(); j ++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

/*
    深度优先搜索
    
    将二维网格看成一个无向图，竖直或水平相邻的 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) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0') {
            return;
        }

        grid[x][y] = '0';
        for (int i = 0; i < 4; i++) {
            int new_x = x + dx[i], new_y = y + dy[i];
            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_2 {
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<PII> q;
        q.push({x, y});
        grid[x][y] = '0';
        while (!q.empty()) {
            PII cur = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                int new_x = cur.first + dx[i], new_y = cur.second + 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, new_y});
                    grid[new_x][new_y] = '0';
                }
            }
        }
    }

private:
    typedef pair<int, int> PII;
    int dx[4] = { -1, 0, 1, 0 };
    int dy[4] = { 0, 1, 0, -1 };
};

int main() {
    // 示例输入
    Solution solution;
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    printGrid(grid);
    cout << "----------" << endl;
    // 计算岛屿数量
    int result = solution.numIslands(grid);
    printGrid(grid);
    cout << "----------" << endl;
    // 打印结果
    cout << "Number of Islands: " << result << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

// rowToString 将一行字节切片转换为带分隔符的字符串
func rowToString(row []byte) string {
	result := ""
	for _, b := range row {
		result += string(b) + " "
	}
	return result[:len(result)-1] // 去掉最后一个多余的空格
}

/*
    深度优先搜索（DFS）：
        遍历整个网格，当遇到一个 '1' 时，表示发现了一个岛屿。
        使用 DFS 标记整个岛屿的所有部分（将 '1' 改为 '0'），避免重复计算。
    标记已访问的岛屿：
        在 DFS 中，将访问过的 '1' 改为 '0'，这样可以避免重复访问。
    遍历网格：
        遍历整个网格，每次发现一个 '1'，计数加1，并使用 DFS 标记整个岛屿。

    时间复杂度：O(mn)
        其中 m 是网格的行数，n 是网格的列数
        每个单元格最多被访问一次，因此时间复杂度为 O(mn)。
    空间复杂度：O(mn)
        DFS 的递归调用栈的深度取决于网格的大小，最坏情况下为 O(mn)。
*/
// numIslands 计算二维网格中的岛屿数量
func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	rows, cols := len(grid), len(grid[0])
	landCount := 0

    // 定义 DFS 函数
    var dfs func(r, c int)
    dfs = func(r, c int) {
        // 边界条件
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0' {
            return
        }

        // 标记当前节点
        grid[r][c] = '0'
        // 遍历各个方向
        // dfs(r-1, c)
        // dfs(r+1, c)
        // dfs(r, c-1)
        // dfs(r, c+1)
        dir := [][]int{{-1,0}, {0,1}, {1,0}, {0,-1}}
        for i := 0; i < 4; i++ {
            new_x, new_y := r + dir[i][0], c + dir[i][1]
            dfs(new_x, new_y);
        }
    }

	// 遍历整个网格
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == '1' {
				// 发现一个岛屿，计数加1，并使用DFS标记整个岛屿
				landCount++
				dfs(r, c)
			}
		}
	}
	return landCount
}

func main() {
    // 测试用例
    testCases := []struct {
        grid     [][]byte
        expected int
    }{
        {
            grid: [][]byte{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'},
            },
            expected: 1,
        },
        {
            grid: [][]byte{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'},
            },
            expected: 3,
        },
    }

    for i, tc := range testCases {
        fmt.Printf("Test Case %d，Input: grid = \n", i+1)
        for _, row := range tc.grid {
            // 使用 rowToString 打印带分隔符的
			fmt.Printf("%s\n", rowToString(row))
        }
        result := numIslands(tc.grid)

        if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)		
        }
    }
}