岛屿问题

• 463.岛屿的周长
• 200.岛屿数量
• 695.岛屿的最大面积
• 827.最大人工岛

如何在网格上做DFS(通用解)

网格问题是这样一类搜索问题：m×n 个小方格，组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。

可以带入二叉树上的DFS遍历方法，分析网格上的DFS

递归的参数和终止条件

//二叉树有两个方向
function traverse(root:TreeNode){
	//判断base case
 	if(root==null)return;
 	//二叉树只有两个相邻节点可选，左子节点，右子节点
 	traverse(root.left);
 	traverse(root.right);
}
//网格有四个方向
function dfs(grid:number[][],x:number,y:number):number{//x为row哪一行，y为col哪一列
	//base case 超出网格范围
	if(x<0 || y<0 || x>=grid.length || y>=grid[0].length) return;
	//递归的方向
	 dfs(grid, x - 1, y); // 上边相邻
	 dfs(grid, x + 1, y); // 下边相邻
	 dfs(grid, x , y-1); // 左边相邻
	 dfs(grid, x , y+1); // 右边相邻
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

如何防止重复遍历？
网格和二叉树的DFS最大的不同是遍历中可能遇到遍历过的结点，所以需要对已经遍历过的节点做标记。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。
每个格子可能右三个取值

• 0海洋格子
• 1陆地格子(没有遍历过)
• 2陆地格子(已经遍历过)

function dfs(grid:number[][],x:number,y:number):number{//x为row哪一行，y为col哪一列
	//base case 超出网格范围
	if(x<0 || y<0 || x>=grid.length || y>=grid[0].length) return;
	if() //可以根据条件增加一些判断，比如已经遍历过就return，或者不是陆地就return等
	grid[r][c] = 2 ; //将格子标记为已经遍历过了
	//递归的方向
	 dfs(grid, x - 1, y); // 上边相邻
	 dfs(grid, x + 1, y); // 下边相邻
	 dfs(grid, x , y-1); // 左边相邻
	 dfs(grid, x , y+1); // 右边相邻
}
1
2
3
4
5
6
7
8
9
10
11

463.岛屿的周长

题目

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

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

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

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

示例 2：

输入：grid = [[1]]
输出：4
1
2

示例 3：

输入：grid = [[1,0]]
输出：4
1
2

提示：

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] 为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/island-perimeter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 -通用模板

岛屿的周长就是计算岛屿的全部边缘，如从1的位置开始,如果走到了边界或者0就+1。如果走到了岛屿就继续往下走。

function islandPerimeter(grid: number[][]): number {
    for(let i=0;i<grid.length;i++){
        for(let j=0;j<grid[0].length;j++){
            if(grid[i][j]==1){ //只有一个岛屿
                return dfs(grid,i,j);
            }
        }
    }
    return 0;
};
function dfs(grid:number[][],x:number,y:number):number{
    if(x<0||y<0||x>=grid.length||y>=grid[0].length)return 1; //超出边界+1
    if(grid[x][y]==0)return 1; //从1->0,边界加1
    if(grid[x][y]==2)return 0; //说明已经走过了不用再走了
    //说明到达新陆地
    grid[x][y] = 2 ;
    return dfs(grid,x+1,y)+dfs(grid,x-1,y)+dfs(grid,x,y-1)+dfs(grid,x,y+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题解2

这道题还有更简单的解法，总周长 = 4 * 土地个数 - 2 * 接壤边的条数
遍历矩阵，遍历到土地，就 land++，如果它的右/下边也是土地，则 border++，遍历结束后代入公式。

function islandPerimeter(grid: number[][]): number {
  let land = 0; // 土地个数
  let border = 0; // 接壤边界的条数

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == 1) {
        land++;
        if (i < grid.length - 1 && grid[i + 1][j] == 1) {
          border++;
        }
        if (j < grid[0].length - 1 && grid[i][j + 1] == 1) {
          border++;
        }
      }
    }
  }
  return 4 * land - 2 * border;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

200.岛屿数量

题目

给你一个由 ‘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
1
2
3
4
5
6
7

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
1
2
3
4
5
6
7

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 ‘0’ 或 ‘1’

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

先从1开始，遍历图，走过的地方标记为2，遍历遇见0和2就返回。一个流程完说明岛屿数量+1。

function numIslands(grid: string[][]): number {
    let count = 0;
    for(let i=0;i<grid.length;i++){
        for(let j=0;j<grid[0].length;j++){
            if(grid[i][j]=='1'){ //开始遍历陆地
                dfs(grid,i,j);
                count++;
            }
        }
    }
    return count;
};

function dfs(grid:string[][],x:number,y:number):void{
    if(x<0||y<0||x>=grid.length||y>=grid[0].length)return; //遇见边界了
    if(grid[x][y]!='1')return; //遇见水了
    //说明当前是陆地
    grid[x][y]='2';//修改已经走过的陆地
    dfs(grid,x-1,y);
    dfs(grid,x+1,y);
    dfs(grid,x,y-1);
    dfs(grid,x,y+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

695.岛屿的最大面积

题目

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
1
2
3

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
1
2

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

和200.岛屿数量非常像，不过这里找到入口开始走岛屿时需要记录岛屿的数量。并且需要维护一个最大值的，每次一个岛屿遍历完后就进行比较。

function maxAreaOfIsland(grid: number[][]): number {
    let max =0;
    for(let i=0;i<grid.length;i++){
        for(let j=0;j<grid[0].length;j++){
            if(grid[i][j]==1){
               max = Math.max(max,dfs(grid,i,j)); 
            }
        }
    }
    return max;
};
function dfs(grid:number[][],x:number,y:number):number{
    if(x<0 ||y<0||x>=grid.length||y>=grid[0].length)return 0; //出界了
    if(grid[x][y]!=1)return 0 ; //已经走过了或者水
    grid[x][y] = 2;
    return dfs(grid,x-1,y) + dfs(grid,x+1,y) + dfs(grid,x,y-1) + dfs(grid,x,y+1)+1;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

827.最大人工岛

题目

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
1
2
3

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
1
2
3

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
1
2
3

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/making-a-large-island
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

暴力解法：遍历地图先尝试将每一个0都变成1后计算面积。先把一个0变为1，计算最大面积，然后将1变回0然后循环。
这样时间复杂度很高，每次变一个1都要重新计算最大岛屿面积。所以可以第一次先遍历依次地图，得出各个岛屿的面积(套用695题)，并用map做记录，key为岛屿编号，value为岛屿面积。第二次从0开始遍历，将0变为1后，并统计周围岛屿的面积，将将其相邻加在一起。

function largestIsland(grid: number[][]): number {
    let n = grid.length;
    let m = grid[0].length;
    let index =2;
    let max = 0;
    let map = new Map<number,number>();
    for(let i=0;i<n;i++){
        for(let j=0;j<m;j++){
            if(grid[i][j]==1){
                let area = dfs(grid,i,j,index);
                map.set(index,area);
                index++;
                max = Math.max(max,area);
            }
        }
    }
    if(max==0)return 1;
    //将0变为1,找这个0周围的1
    for(let i=0;i<n;i++){
        for(let j=0;j<m;j++){
            if(grid[i][j]==0){
                let neighbour = findNeighbour(grid,i,j);
                if(neighbour.size<0)continue; //当前周围都是0，开始找下一个
                let total = 1 ;
                for(let key of neighbour){
                    total += map.get(key)
                }
                max = Math.max(max,total);
            }
        }
    }
    return max;
};
//找当前海洋格子的相邻岛屿
function findNeighbour(grid:number[][],x:number,y:number):Set<number>{
    let set = new Set<number>()
    if(inArea(grid,x-1,y) && grid[x-1][y]!=0)set.add(grid[x-1][y]);
    if(inArea(grid,x+1,y) && grid[x+1][y]!=0)set.add(grid[x+1][y]);
    if(inArea(grid,x,y-1) && grid[x][y-1]!=0)set.add(grid[x][y-1]);
    if(inArea(grid,x,y+1) && grid[x][y+1]!=0)set.add(grid[x][y+1]);
    return set;
}
//index为每个岛屿的编号,计算每个岛屿的面积
function dfs(grid:number[][],x:number,y:number,index:number):number{
    if(!inArea(grid,x,y))return 0; //出界了
    if(grid[x][y]!=1)return 0 ; 
    grid[x][y] = index;
    return dfs(grid,x-1,y,index) + dfs(grid,x+1,y,index) + dfs(grid,x,y-1,index) + dfs(grid,x,y+1,index)+1;  
}
function inArea(grid:number[][],x:number,y:number):boolean{
    return x>=0 && x<grid.length && y>=0 && y<grid[0].length;
}
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
47
48
49
50
51
52