leetcode 200. Number of Islands（岛屿的数量）

https://leetcode.com/problems/number-of-islands/

 

一、问题描述

给定一个二维数组，其元素均为'1'和'0'，分别代表陆地和水，现在要计算数组中岛屿的数量。

被水包围的就是岛屿，此外，数组的四条边界均被水包围。

PS：某司的校招机试也出了这道题，该题反过来求一块有水有陆地的地域中湖泊的数量，解法完全一样。

 

测试用例：

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3

 

二、代码实现

总体思路是进行两层for循环遍历二维数组的所有元素，对于每个遍历到的元素，如果是'1'，将其置为'0'，并且将它上下左右相邻的S也置为'0'； 如果是'0'，直接continue跳过该元素。

class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int res = 0; // 计数器（岛屿的数量） for (int i=0; i < grid.length; i++) { for (int j=0; j < grid[0].length; j++) { if (grid[i][j] == '1') { dfs(i, j, grid); res ++; } } } return res; } private void dfs(int i, int j, char[][] grid) { grid[i][j] = '0'; if (i-1 >= 0 && grid[i-1][j] == '1') { // 上 dfs(i-1, j, grid); } if (i+1 < grid.length && grid[i+1][j] == '1') { // 下 dfs(i+1, j, grid); } if (j-1 >= 0 && grid[i][j-1] == '1') { // 左 dfs(i, j-1, grid); } if (j+1 < grid[0].length && grid[i][j+1] == '1') { // 右 dfs(i, j+1, grid); } } }