题目描述

给你一个由 ‘H’（陆地）和 ‘S’（湖泊）组成的的二维网格，请你计算网格中湖泊的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

• 示例 1:
  • 输入
    4 5
    SSSSH
    SSHSH
    SSHHH
    HHHHH
  • 输出
    1
• 示例 2:
  • 输入:
    4 5
    SSHHH
    SSHHH
    HHSHH
    HHHSS
  • 输出
    3

解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

分析

深度优先搜索

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().trim().split(" ");
        int r = Integer.parseInt(s[0]);
        int c = Integer.parseInt(s[1]);

        int[][] arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            String str = sc.nextLine().trim();
            for (int j = 0; j < c; j++) {
                if (str.charAt(j)=='S') arr[i][j] = 0;
                else arr[i][j] = 1;
            }
        }
        //上面是输入数据
        
// 查看dfs前的数组
// for (int i = 0; i < r; i++)
// System.out.println(Arrays.toString(arr[i]));

        Main demo = new Main2();
        int j = demo.numLakes(arr);
        System.out.println(j);
// 查看dfs后的数组
// for (int i = 0; i < r; i++)
// System.out.println(Arrays.toString(arr[i]));
        
    }
	//计算岛屿数量
    public int numLakes(int[][] grid){
        if(grid == null||grid.length == 0) return 0;
        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; r++) {
            for (int c = 0; c < nc; c++) {
                if(grid[r][c] == 0){
                    num_islands++;
                    dfs(grid,r,c);
                }
            }
        }
        return num_islands;
    }
	//深度优先搜索，将查看过的置为1
    private void dfs(int[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;
        if(r<0||c<0||r>=nr||c>=nc||grid[r][c] == 1) return;
        grid[r][c] = 1;
        dfs(grid,r-1,c);
        dfs(grid,r+1,c);
        dfs(grid,r,c-1);
        dfs(grid,r,c+1);
    }
}

输入：
4 5
SSHHH
SSHHH
HHSHH
HHHSS

输出：
[0, 0, 1, 1, 1]
[0, 0, 1, 1, 1]
[1, 1, 0, 1, 1]
[1, 1, 1, 0, 0]
3

复杂度分析

• 时间复杂度：O(MN)，其中 M和 N 分别为行数和列数。
• 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

PS：本人水平有限，文中如有错漏，欢迎大家指出。转载请注明来源。