【代码随想录】刷题记录(114)-岛屿数量(深搜)

题目描述：

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

3

提示信息

根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。

数据范围：

1 <= N, M <= 50

我的作答：

和查找矩阵中1的元素的最大区别在于，如果1结块出现，只能算一个；所以深搜的目的是找到“最外面”的1,1和0的分界处；

import sys

def dfs(grid, visited, x, y):
    direction = [[1, 0], [0, 1], [-1, 0], [0, -1]] #方向右，下，左，上
    for i, j in direction:
        next_x = x+i #左右方向的邻接元素
        next_y = y+j #上下方向的邻接元素
        if next_x<0 or next_x>len(grid)-1 or next_y<0 or next_y>len(grid[0])-1:
            continue #查到边界的时候跳过
        if not visited[next_x][next_y] and grid[next_x][next_y]:
            visited[next_x][next_y] = True #如果邻接元素是1，就让邻接元素再往现有方向搜索到0-1分界处
            dfs(grid, visited, next_x, next_y)

N, M = map(int, input().split())
visited = [[False]*M for _ in range(N)]
grid = []
res = 0
for _ in range(N):
    grid.append(list(map(int, input().split())))
for i in range(N): #遍历矩阵里的每个元素
    for j in range(M):
        if not visited[i][j] and grid[i][j]:
            visited[i][j] = True #遍历到第一个1就+1，然后把邻接的所有1标为True
            res += 1
            dfs(grid, visited, i, j)
print(res)

参考：

direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 四个方向：上、右、下、左


def dfs(grid, visited, x, y):
    """
    对一块陆地进行深度优先遍历并标记
    """
    # 在调用前增加判断终止条件
    if visited[x][y] or grid[x][y] == 0:
        return
    visited[x][y] = True

    for i, j in direction:
        next_x = x + i
        next_y = y + j
        # 下标越界，跳过
        if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):
            continue
        # 由于判断条件放在了方法首部，此处直接调用dfs方法
        dfs(grid, visited, next_x, next_y)


if __name__ == '__main__':
    # 版本二
    n, m = map(int, input().split())

    # 邻接矩阵
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))

    # 访问表
    visited = [[False] * m for _ in range(n)]

    res = 0
    for i in range(n):
        for j in range(m):
            # 判断：如果当前节点是陆地，res+1并标记访问该节点，使用深度搜索标记相邻陆地。
            if grid[i][j] == 1 and not visited[i][j]:
                res += 1
                dfs(grid, visited, i, j)

    print(res)