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
由于markdown语法的原因，无法将一行代码添加为代码形式，请在每个Solution类中加入private int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};作为遍历的四个方向。
- Method：DFS AC
class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
int height = grid.length;
int width = grid[0].length;
boolean[][] used = new boolean[height][width];
int count = 0;
LinkedList<Integer> q = new LinkedList<>();
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(grid[i][j] == '1' && !used[i][j]){
count ++;
bfs(grid, used, i, j);
}
}
}
return count;
}
private void bfs(char[][] grid, boolean[][] used, int row, int col){
if(!(row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == '1' && !used[row][col]))
return;
used[row][col] = true;
for(int i = 0; i < 4; i++){
bfs(grid, used, row + dir[i][0], col + dir[i][1]);
}
}
}- Method 2: BFS TLE
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
if(grid == null || grid.length == 0) return 0;
int height = grid.length;
int width = grid[0].length;
boolean[][] used = new boolean[height][width];
LinkedList<Integer> queue = new LinkedList<>();
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++){
if(grid[i][j] == '0' || used[i][j]) continue;
else{
count++;
queue.add(i * width + j);
while(!queue.isEmpty()){
Integer cnt = queue.poll();
int row = cnt / width;
int col = cnt % width;
used[row][col] = true;
for(int p = 0; p < 4; p++){
int tempRow = row, tempCol = col;
tempRow += dir[p][0];
tempCol += dir[p][1];
if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !used[tempRow][tempCol] && grid[tempRow][tempCol] == '1')
queue.add(tempRow * width + tempCol);
}
}
}
}
}
return count;
}
}- 使用bfs
class Solution {
public int numIslands(char[][] grid) {
if(grid.length == 0 || grid[0].length == 0) return 0;
int row = grid.length, col = grid[0].length;
boolean[][] visited = new boolean[row][col];
int result = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(grid[i][j] == '1' && !visited[i][j]){
visit(grid, row, col, i, j, visited);
result ++;
}
}
}
return result;
}
private void visit(char[][] grid, int row, int col, int i, int j, boolean[][] visited){
visited[i][j] = true;
int tempRow = 0, tempCol = 0;
for(int d = 0; d < 4; d++){
tempRow = i + dir[d][0];
tempCol = j + dir[d][1];
if(tempRow >= 0 && tempRow < row && tempCol >= 0 && tempCol < col && grid[tempRow][tempCol] == '1' && !visited[tempRow][tempCol]){
visit(grid, row, col, tempRow, tempCol, visited);
}
}
}
}-
Method 1: dfs
class Solution { private int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; private int height; private int width; public int numIslands(char[][] grid) { if(grid == null || grid.length == 0 || grid[0].length == 0) return 0; this.height = grid.length; this.width = grid[0].length; int res = 0; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == '0') continue; dfs(grid, i, j); res++; } } return res; } private void dfs(char[][] grid, int row, int col){ grid[row][col] = '0'; int tx = 0, ty = 0; for(int i = 0; i < 4; i++){ tx = row + dir[i][0]; ty = col + dir[i][1]; if(tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] != '0') dfs(grid, tx, ty); } } }
- Method 2: union-find
- For any single node, we can check its right side node and bottom side node and add them to union find set.
- There are two tricks for optimize union find set:
- path compression.
- merge using rank.
class Solution { private int[] uf; private static int[][] dir = new int[][]{{0, 1}, {1, 0}}; public int numIslands(char[][] grid) { if(grid == null || grid.length == 0 || grid[0].length == 0) return 0; int height = grid.length; int width = grid[0].length; uf = new int[height * width]; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == '1') uf[i * width + j] = i * width + j; else uf[i * width + j] = -1; } } for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == '0') continue; int tx = 0, ty = 0; for(int d = 0; d < 2; d++){ tx = i + dir[d][0]; ty = j + dir[d][1]; if(tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] == '1'){ union(i * width + j, tx * width + ty); } } } } int res = 0; for(int i = 0; i < uf.length; i++){ if(uf[i] == i) res++; } return res; } private void union(int i, int j){ int p = find(i); int q = find(j); uf[p] = q; } private int find(int i){ if(uf[i] != i){ uf[i] = find(uf[i]); } return uf[i]; } }
- Method 2: union-find
- Method 1: uf
class Solution { private int[] uf; private static final int[][] dir = new int[][]{{0, 1}, {1, 0}}; public int numIslands(char[][] grid) { if(grid == null || grid.length == 0 || grid[0].length == 0) return 0; int height = grid.length; int width = grid[0].length; this.uf = new int[height * width]; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == '1') uf[i * width + j] = i * width + j; else uf[i * width + j] = -1; } } for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++){ if(grid[i][j] == '0') continue; int tx = 0, ty = 0; for(int d = 0; d < 2; d++){ tx = i + dir[d][0]; ty = j + dir[d][1]; if(tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] == '1'){ union(i * width + j, tx * width + ty); } } } } int count = 0; for(int i = 0; i < uf.length; i++){ if(uf[i] == i) count++; } return count; } private int find(int i){ if(uf[i] != i){ uf[i] = find(uf[i]); } return uf[i]; } private void union(int i, int j){ int p = find(i); int q = find(j); uf[p] = q; } }