跳至主要內容

0463. 岛屿的周长

ITCharge大约 2 分钟

0463. 岛屿的周长open in new window

  • 标签:深度优先搜索、广度优先搜索、数组、矩阵
  • 难度:简单

题目链接

题目大意

描述:给定一个 row * col 大小的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地,grid[i][j] = 0 表示水域。

网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(多个表示陆地的格子相连组成)。

岛屿内部中没有「湖」(指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。

要求:计算这个岛屿的周长。

说明

  • row==grid.lengthrow == grid.length
  • col==grid[i].lengthcol == grid[i].length
  • 1<=row,col<=1001 <= row, col <= 100
  • grid[i][j]grid[i][j]0011

示例

  • 示例 1:
输入:grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出:16
解释:它的周长是上面图片中的 16 个黄色的边
  • 示例 2:
输入:grid = [[1]]
输出:4

解题思路

思路 1:广度优先搜索

  1. 使用整形变量 count 存储周长,使用队列 queue 用于进行广度优先搜索。
  2. 遍历一遍二维数组 grid,对 grid[row][col] == 1 的区域进行广度优先搜索。
  3. 先将起始点 (row, col) 加入队列。
  4. 如果队列不为空,则取出队头坐标 (row, col)。先将 (row, col) 标记为 2,避免重复统计。
  5. 然后遍历上、下、左、右四个方向的相邻区域,如果遇到边界或者水域,则周长加 1。
  6. 如果相邻区域 grid[new_row][new_col] == 1,则将其赋值为 2,并将坐标加入队列。
  7. 继续执行 4 ~ 6 步,直到队列为空时返回 count

思路 1:代码

class Solution:
    def bfs(self, grid, rows, cols, row, col):
        directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        queue = collections.deque([(row, col)])

        count = 0
        while queue:
            row, col = queue.popleft()
            # 避免重复统计
            grid[row][col] = 2
            for direct in directs:
                new_row = row + direct[0]
                new_col = col + direct[1]
                # 遇到边界或者水域,则周长加 1
                if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= cols or grid[new_row][new_col] == 0:
                    count += 1
                # 相邻区域为陆地,则将其标记为 2,加入队列
                elif grid[new_row][new_col] == 1:
                    grid[new_row][new_col] = 2
                    queue.append((new_row, new_col))
                # 相邻区域为 2 的情况不做处理
        return count

    def islandPerimeter(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    return self.bfs(grid, rows, cols, row, col)

思路 1:复杂度分析

  • 时间复杂度O(n×m)O(n \times m),其中 mmnn 分别为行数和列数。
  • 空间复杂度O(n×m)O(n \times m)

参考资料