Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Example 1
Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output: 1
Example 2
Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
m == grid.lengthn == grid[i].length1 <= m, n <= 300DFS from each unvisited land cell, marking visited cells as '0' or '#'.
public int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
dfs(grid, r, c);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1')
return;
grid[r][c] = '0'; // mark visited
dfs(grid, r+1, c); dfs(grid, r-1, c);
dfs(grid, r, c+1); dfs(grid, r, c-1);
}Time: O(m*n) · Space: O(m*n) recursion stack