题目描述

给你一个由 ‘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：本人水平有限，文中如有错漏，欢迎大家指出。转载请注明来源。