Graphs
Count Number of Islands
You are given a 2D grid grid where:
'1'represents land, and'0'represents water.
Your task is to count and return the number of islands in the grid.
Definition:
An island is formed by connecting adjacent land cells horizontally or vertically. The grid is surrounded by water, meaning all edges of the grid are considered water.
Examples:
Example 1:
- Input:css
grid = [ ["0","1","1","1","0"], ["0","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] - Output:
1
Example 2:
- Input:css
grid = [ ["1","1","0","0","1"], ["1","1","0","0","1"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] - Output:
4
Constraints:
1 <= grid.length, grid[i].length <= 100grid[i][j]is either'0'(water) or'1'(land).
public int numIslands(char[][] grid) {
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) {
if (
i < 0 ||
j < 0 ||
i >= grid.length ||
j >= grid[0].length ||
grid[i][j] == '0'
) {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i - 1, j);
dfs(grid, i, j - 1);
}
