200. 岛屿数量

发布于：2024-07-02 ⋅ 阅读:(17) ⋅ 点赞:(0)

题目

给你一个由 1（陆地）和 0（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

输出：1

示例 2：

输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]

输出：3

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] 的值为 0 或 1

代码

完整代码

void islandClear(char** grid, int gridSize, int* gridColSize, int x, int y)
{
    grid[x][y] = '0';
    if(x + 1 < gridSize && grid[x+1][y] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x+1, y);
    }
    if(y + 1 < *gridColSize && grid[x][y+1] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x, y+1);
    }
    if(x > 0 && grid[x-1][y] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x-1, y);
    }
    if(y > 0 && grid[x][y-1] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x, y-1);
    }
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int isLandCnt = 0;
    for (int i = 0; i < gridSize; i++)
    {
        for (int j = 0; j < *gridColSize; j++)
        {
            if(grid[i][j] == '1')
            {
                isLandCnt++;
                islandClear(grid, gridSize, gridColSize, i, j);
            }
        }
    }
    return isLandCnt;
}

思路分析

这套代码用了*深度优先搜索(DFS)*方法。
代码的整体逻辑是遍历二维网格，当遇到‘1’时，表示找到一个新的岛屿，计数器增加，同时调用islandClear函数，将与该陆地相连的所有陆地都置为‘0’，表示已访问过的区域，避免重复计数。

拆解分析

  1. islandClear函数
void islandClear(char** grid, int gridSize, int* gridColSize, int x, int y)
{
    grid[x][y] = '0';
    if(x + 1 < gridSize && grid[x+1][y] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x+1, y);
    }
    if(y + 1 < *gridColSize && grid[x][y+1] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x, y+1);
    }
    if(x > 0 && grid[x-1][y] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x-1, y);
    }
    if(y > 0 && grid[x][y-1] == '1')
    {
        islandClear(grid, gridSize, gridColSize, x, y-1);
    }
}

islandClear函数的解析：该函数用于清除与当前陆地相连的所有陆地。它通过递归的方式，将四个方向相邻的陆地置为‘0’，表示已访问。

  1. numIslands函数中的双重循环
int numIslands(char** grid, int gridSize, int* gridColSize) {
    int isLandCnt = 0;
    for (int i = 0; i < gridSize; i++)
    {
        for (int j = 0; j < *gridColSize; j++)
        {
            if(grid[i][j] == '1')
            {
                isLandCnt++;
                islandClear(grid, gridSize, gridColSize, i, j);
            }
        }
    }
    return isLandCnt;
}

双重循环的解析：外层循环遍历网格的每一行，内层循环遍历每一列。当遇到‘1’时，表示发现一个新的岛屿，计数器增加，并调用islandClear函数，清除与该陆地相连的所有陆地。

复杂度分析

  • 时间复杂度：O(m * n)，其中m和n分别是网格的行数和列数。每个格子最多只会被访问一次。
  • 空间复杂度：O(m * n)，在最坏情况下，递归调用栈的深度可能达到网格中所有陆地格子的数量。

一题多解

广度优先搜索(BFS)

完整代码

#include <stdbool.h>

typedef struct {
    int x, y;
} Point;

bool isValid(char** grid, int gridSize, int* gridColSize, int x, int y) {
    return x >= 0 && x < gridSize && y >= 0 && y < *gridColSize && grid[x][y] == '1';
}

void bfs(char** grid, int gridSize, int* gridColSize, int startX, int startY) {
    Point queue[gridSize * (*gridColSize)];
    int front = 0, rear = 0;
    queue[rear++] = (Point){startX, startY};
    grid[startX][startY] = '0';

    while (front < rear) {
        Point p = queue[front++];
        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; i++) {
            int newX = p.x + directions[i][0];
            int newY = p.y + directions[i][1];
            if (isValid(grid, gridSize, gridColSize, newX, newY)) {
                grid[newX][newY] = '0';
                queue[rear++] = (Point){newX, newY};
            }
        }
    }
}

int numIslandsBFS(char** grid, int gridSize, int* gridColSize) {
    int isLandCnt = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < *gridColSize; j++) {
            if (grid[i][j] == '1') {
                isLandCnt++;
                bfs(grid, gridSize, gridColSize, i, j);
            }
        }
    }
    return isLandCnt;
}

思路分析

这套代码用了*广度优先搜索(BFS)*方法。
代码的整体逻辑与DFS类似，但在发现新的岛屿后，通过队列进行广度优先搜索，将与该陆地相连的所有陆地都置为‘0’，表示已访问过的区域。

拆解分析

  1. isValid函数
bool isValid(char** grid, int gridSize, int* gridColSize, int x, int y) {
    return x >= 0 && x < gridSize && y >= 0 && y < *gridColSize && grid[x][y] == '1';
}

isValid函数的解析：用于判断某个坐标是否在网格范围内且对应位置为‘1’。

  1. bfs函数
void bfs(char** grid, int gridSize, int* gridColSize, int startX, int startY) {
    Point queue[gridSize * (*gridColSize)];
    int front = 0, rear = 0;
    queue[rear++] = (Point){startX, startY};
    grid[startX][startY] = '0';

    while (front < rear) {
        Point p = queue[front++];
        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; i++) {
            int newX = p.x + directions[i][0];
            int newY = p.y + directions[i][1];
            if (isValid(grid, gridSize, gridColSize, newX, newY)) {
                grid[newX][newY] = '0';
                queue[rear++] = (Point){newX, newY};
            }
        }
    }
}

bfs函数的解析：通过队列进行广度优先搜索，将与当前陆地相连的所有陆地置为‘0’。队列中每次取出一个点，并将该点的四个方向相邻的陆地加入队列，直到队列为空。

  1. numIslandsBFS函数中的双重循环
int numIslandsBFS(char** grid, int gridSize, int* gridColSize) {
    int isLandCnt = 0;
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < *gridColSize; j++) {
            if (grid[i][j] == '1') {
                isLandCnt++;
                bfs(grid, gridSize, gridColSize, i, j);
            }
        }
    }
    return isLandCnt;
}

*双重循环的解析

：外层循环遍历网格的每一行，内层循环遍历每一列。当遇到‘1’时，表示发现一个新的岛屿，计数器增加，并调用bfs函数，清除与该陆地相连的所有陆地。*

复杂度分析

  • 时间复杂度：O(m * n)，其中m和n分别是网格的行数和列数。每个格子最多只会被访问一次。
  • 空间复杂度：O(m * n)，在最坏情况下，队列的大小可能达到网格中所有陆地格子的数量。

结果

DFS

在这里插入图片描述

BFS

在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布