|
5 | 5 |
|
6 | 6 | ##题目大意 |
7 | 7 |
|
8 | | -给定一个`row * col` 大小的二维网格地图`grid` ，其中：`grid[i][j] = 1` 表示陆地，`grid[i][j] = 0` 表示水域。 |
| 8 | +**描述**：给定一个`row * col` 大小的二维网格地图`grid` ，其中：`grid[i][j] = 1` 表示陆地，`grid[i][j] = 0` 表示水域。 |
9 | 9 |
|
10 | 10 | 网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（多个表示陆地的格子相连组成）。 |
11 | 11 |
|
12 | 12 | 岛屿内部中没有「湖」（指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。 |
13 | 13 |
|
14 | | -要求：计算这个岛屿的周长。 |
| 14 | +**要求**：计算这个岛屿的周长。 |
15 | 15 |
|
16 | | -示例：下图周长为 16。 |
| 16 | +**说明**： |
| 17 | + |
| 18 | +- $row == grid.length$。 |
| 19 | +- $col == grid[i].length$。 |
| 20 | +- $1 <= row, col <= 100$。 |
| 21 | +- $grid[i][j]$ 为 $0$ 或 $1$。 |
| 22 | + |
| 23 | +**示例**： |
17 | 24 |
|
18 | 25 |  |
19 | 26 |
|
| 27 | +```Python |
| 28 | +输入：grid= [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] |
| 29 | +输出：16 |
| 30 | +解释：它的周长是上面图片中的16 个黄色的边 |
| 31 | + |
| 32 | + |
| 33 | +输入：grid= [[1]] |
| 34 | +输出：4 |
| 35 | +``` |
| 36 | + |
20 | 37 | ##解题思路 |
21 | 38 |
|
22 | | -可以使用广度优先搜索求解。具体做法如下： |
| 39 | +###思路 1：广度优先搜索 |
23 | 40 |
|
24 | 41 | 1. 使用整形变量`count` 存储周长，使用队列`queue` 用于进行广度优先搜索。 |
25 | 42 | 2. 遍历一遍二维数组`grid`，对`grid[row][col] == 1` 的区域进行广度优先搜索。 |
|
29 | 46 | 6. 如果相邻区域`grid[new_row][new_col] == 1`，则将其赋值为`2`，并将坐标加入队列。 |
30 | 47 | 7. 继续执行 4 ~ 6 步，直到队列为空时返回`count`。 |
31 | 48 |
|
32 | | -##代码 |
| 49 | +###思路 1：代码 |
33 | 50 |
|
34 | 51 | ```Python |
35 | 52 | classSolution: |
@@ -63,6 +80,11 @@ class Solution: |
63 | 80 | returnself.bfs(grid, rows, cols, row, col) |
64 | 81 | ``` |
65 | 82 |
|
| 83 | +###思路 1：复杂度分析 |
| 84 | + |
| 85 | +-**时间复杂度**：$O(n \times m)$，其中 $m$ 和 $n$ 分别为行数和列数。 |
| 86 | +-**空间复杂度**：$O(n \times m)$。 |
| 87 | + |
66 | 88 | ##参考资料 |
67 | 89 |
|
68 | 90 | - 【题解】[Golang BFS 实现，性能比dfs要高 - 岛屿的周长 - 力扣](https://leetcode.cn/problems/island-perimeter/solution/golang-bfs-shi-xian-xing-neng-bi-dfsyao-nln2g/) |