Question
1 1 1 1 1 0
1 0 1 0 0 1
1 0 1 0 0 1
1 1 0 1 1 1
1 is earth, 0 is water.
i) count the number of 'islands' that the matrix has.
ii) count the number of 'lakes' that the matrix has i.e. connected clump of zeros that is entirely surrounded by a single island
Solution
这是Number of Islands的升级版。关键在于lake的定义,必须被同一个岛包围。
所以我们在dfs遍历岛的时候,给相同的岛同样的标号。然后在遍历水的时候,检查包围的岛是否是相同标号。
import java.util.*;
import java.io.*; public class Islands {
private static final int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}}; public static void main(String[] args) {
int[][] island = {
{1, 1, 1, 1, 1, 0},
{1, 0, 1, 0, 0, 1},
{1, 0, 1, 0, 0, 1},
{1, 1, 0, 1, 1, 1}
};
int m = island.length, n = island[0].length;
// Calculate island number
int color = 2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (island[i][j] == 1) {
dfs(island, color, i, j);
color++;
}
}
}
int islandNum = color - 2;
int lakeNum = 0;
int surround = -2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (island[i][j] == 0) {
if (dfs2(island, surround, i, j)) {
lakeNum++;
}
}
}
}
System.out.println(islandNum);
System.out.println(lakeNum); } private static void dfs(int[][] island, int color, int x, int y) {
int m = island.length, n = island[0].length;
island[x][y] = color;
int newX, newY;
for (int i = 0; i < 4; i++) {
newX = x + directions[i][0];
newY = y + directions[i][1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n)
continue;
if (island[newX][newY] != 1)
continue;
dfs(island, color, newX, newY);
}
} private static boolean dfs2(int[][] island, int surround, int x, int y) {
int m = island.length, n = island[0].length;
island[x][y] = -1;
int newX, newY;
for (int i = 0; i < 4; i++) {
newX = x + directions[i][0];
newY = y + directions[i][1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n)
continue;
int color = island[newX][newY];
if (color == -1)
continue;
if (color != 0) {
// This point is earth
if (surround == -2) {
surround = color;
} else if (surround != color) {
return false;
}
} else {
if (!dfs2(island, surround, newX, newY))
return false;
} }
return true;
}
}