Number of Islande
出处
给一个01矩阵,求不同的岛屿的个数。
0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
Solution
Use DFS to find the number of connected components of the graph. One full DFS traversal of a node yields a connected component, which could be viewed as an island containing adjacent nodes (by left,right,up and down). Then we could traverse other isolated node excluded from this connected component, in the same manner.
Complexity
时间复杂度 O(n),空间复杂度 O(n)
Code
其实可以不用 visit 访问过的设为 0 即可
public class Solution {
private void detectIsland(char[][] grid, int i, int j) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
if (i > 0) {
detectIsland(grid, i-1, j);
}
if (i < grid.length-1) {
detectIsland(grid, i+1, j);
}
if (j < grid[0].length-1) {
detectIsland(grid, i, j+1);
}
if (j > 0) {
detectIsland(grid, i, j-1);
}
} else {
return;
}
}
public int numIslands(char[][] grid) {
if (grid==null || grid.length==0 || grid[0].length==0) {
return 0;
}
int numberOfIslands = 0;
for (int i = 0;i != grid.length;i++) {
for (int j = 0;j != grid[0].length;j++) {
if (grid[i][j] == '1') {
numberOfIslands++;
detectIsland(grid, i, j);
}
}
}
return numberOfIslands;
}
}
public class Solution {
/**
* @param grid a boolean 2D matrix
* @return an integer
*/
public int numIslands(boolean[][] grid) {
if(grid == null || grid.length == 0) {
return 0;
}
final int N = grid.length;
final int M = grid[0].length;
final boolean visited[][] = new boolean[N][M];
int count = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(grid[i][j] && !visited[i][j]) {
dfs(grid, i, j, visited);
count++;
}
}
}
return count;
}
private void dfs(boolean[][] grid, int i, int j, boolean[][] visited) {
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
return;
} else if (visited[i][j] || !grid[i][j] ) {
return;
}
visited[i][j] = true;
dfs(grid, i - 1, j, visited);
dfs(grid, i + 1, j, visited);
dfs(grid, i, j - 1, visited);
dfs(grid, i, j + 1, visited);
}
}