1.简述:
给你一个‘1’(陆地)和 由“0”(水)组成的二维网格,请计算网格中岛屿的数量。
岛屿总是被水包围,每个岛屿只能由水平方向和/或垂直方向相邻的陆地连接而成。
另外,你可以假设网格的四个边缘被水包围。
示例 1:
输入:grid = [
“1”、“1”、“1”、“1”、“0”
“1”、“1”、“0”、“1”、“0”
“1”,“1”,“0”,“0”,“0”,“0”
“0”,“0”,“0”,“0”,“0”,“0”
]
输出:1
示例 2:
输入:grid = [
“1”,“1”,“0”,“0”,“0”,“0”
“1”,“1”,“0”,“0”,“0”,“0”
“0”、“0”、“1”、“0”、“0”、“0”
“0”,“0”,“0”,“1”,“1”
]
输出:3
2.实现代码:
class Solution { void dfs(char[][] 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] == '0') { return; } grid[r][c] = '0'; dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1); } public int numIslands(char[][] 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] == '1') { ++num_islands; dfs(grid, r, c); } } } return num_islands; }}
![](/images/780-200-2.jpg)