👦 463.岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
思路
基本思想
题目中只给出了一个岛屿，需要统计岛屿的周长，需要注意的是，只有遇到边界或者海洋时才需要统计周长，也就是下图中的情况
所以需要对岛屿的遍历问题进行简单的改造，一旦当前位置是海洋或者边界，那么当前位置就会出现一个岛屿的边，此时就会使得周长+1，所以返回时需要对返回的情况加以区分，遇到海洋或者边界时周长+1，此时返回1，遇到已遍历的陆地不需要对周长+1，此时返回0
所以此时岛屿的遍历函数需要有返回值，并且需要统计当前节点的上下左右哪些位置会造成周长+1，将这些情况统计出来，最终就是岛屿的周长
执行流程
- 正常的遍历岛屿，遇到陆地节点就将其相邻的所有陆地找出来，形成一个岛屿
- 遍历陆地的相邻节点时，有以下几种情况：
- 当前节点超出边界或者是海洋节点，此时周长需要+1，返回1
- 当前节点是已经遍历过的节点，此时周长不需要+1，返回0
- 当前节点遍历过了之后，看上下左右四个方向是否能出现对周长产生增益的节点，也就是海洋或者边界，如果有的话就返回1
- 统计结束返回最终的结果
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public:
//当前节点是陆地，就有可能需要统计边界
//统计过后将遍历过的节点进行记录
//用来记录周长
int length;
int islandPerimeter(vector<vector<int>>& grid) {
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[0].size();++j){
if(grid[i][j]==1){
dfs(grid,i,j);
}
}
}
return length;
}
int dfs(vector<vector<int>>& grid,int x,int y){
//超过边界、已访问过、海洋节点都会返回
//当前位置超过边界或者是海洋，说明此位置需要统计周长
if(x<0||y<0||x>=grid.size()||y>=grid[0].size()||grid[x][y]==0)
return 1;
//当前位置已访问过，不需要统计周长
if(grid[x][y]==2)
return 0;
//到这里说明此位置是陆地，需要访问
grid[x][y]=2;
int up=dfs(grid,x-1,y);
int down=dfs(grid,x+1,y);
int left=dfs(grid,x,y-1);
int right=dfs(grid,x,y+1);
//上面是海洋或者边界，周长+1
if(up)
++length;
//如果下面是海洋或者边界，周长+1
if(down)
++length;
//如果左边是海洋或者边界，周长+1
if(left)
++length;
//如果右边是海洋或者边界，周长+1
if(right)
++length;
return 0;
}
};
|
总结
将岛屿遍历的问题进行转换，一旦当前节点的上下左右出现边界或者海洋节点，此时周长需要+1，所以返回条件需要进行区分，然后将上下左右能够使得周长+1的情况区分出来，分别累加到周长上
