Given a 2d grid map of ‘1‘
s (land) and ‘0‘
s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
count形容的是一整个岛的数量,直接在DFS结束后++就行了,不需要在DFS内部++。防止重复也是加到set里了,不需要在内部++
class Solution { public int numIslands(char[][] grid) { //cc if (grid == null || grid.length == 0 || grid[0].length == 0) return 0; int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == ‘1‘) { dfs(grid, i, j); count++; } } } return count; } public void dfs(char[][] grid, int i, int j) { //cc if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return ; if (grid[i][j] == ‘1‘) { grid[i][j] = ‘0‘; dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); } } }
200. Number of Islands 200.岛屿数(可以形状一样)
原文:https://www.cnblogs.com/immiao0319/p/13257937.html