题目
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
解法思路（一）
- 如果发现一格还没有探索过的陆地，就在这格陆地上洒水，让水在这片陆地上蔓延；
- 具体做法是：遍历二维数组，如果当前格子是陆地且没被访问过，那么就将该格子标记为已访问过，并在当前格子的上下左右找陆地；
解法实现（一）
时间复杂度
- O(n*m)；
空间复杂度
- O(n*m)；
关键字
floodfill 递归 回溯 深度优先遍历 二维数组 上下左右
实现细节
- 注意上下左右的坐标通过二维数组
d找到；
package leetcode._200;
public class Solution200_1 {
private int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;
private boolean[][] visited;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
res ++;
dfs(grid, i, j);
}
}
}
return res;
}
private void dfs(char[][] grid, int i, int j) {
visited[i][j] = true;
for (int k = 0; k < 4; k++) {
int newI = i + d[k][0];
int newJ = j + d[k][1];
if (inArea(newI, newJ) && grid[newI][newJ] == '1' && !visited[newI][newJ]) {
dfs(grid, newI, newJ);
}
}
}
private boolean inArea(int newI, int newJ) {
return newI >=0 && newI < m && newJ >= 0 && newJ < n;
}
public static void main(String[] args) {
char grid1[][] = {
{'1','1','1','1','0'},
{'1','1','0','1','0'},
{'1','1','0','0','0'},
{'0','0','0','0','0'}
};
System.out.println((new Solution200_1()).numIslands(grid1));
// 1
// ---
char grid2[][] = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
System.out.println((new Solution200_1()).numIslands(grid2));
// 3
}
}
