Calculate Number Of Islands And Lakes 解答

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遍历岛的时候，给相同的岛同样的标号。然后在遍历水的时候，检查包围的岛是否是相同标号。

 1 import java.util.*;
 2 import java.io.*;
 3 
 4 public class Islands {
 5     private static final int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
 6 
 7     public static void main(String[] args) {
 8         int[][] island = {
 9             {1, 1, 1, 1, 1, 0},
10             {1, 0, 1, 0, 0, 1},
11             {1, 0, 1, 0, 0, 1},
12             {1, 1, 0, 1, 1, 1}
13         };
14         int m = island.length, n = island[0].length;
15         // Calculate island number
16         int color = 2;
17         for (int i = 0; i < m; i++) {
18             for (int j = 0; j < n; j++) {
19                 if (island[i][j] == 1) {
20                     dfs(island, color, i, j);
21                     color++;
22                 }
23             }
24         }
25         int islandNum = color - 2;
26         int lakeNum = 0;
27         int surround = -2;
28         for (int i = 0; i < m; i++) {
29             for (int j = 0; j < n; j++) {
30                 if (island[i][j] == 0) {
31                     if (dfs2(island, surround, i, j)) {
32                         lakeNum++;
33                     }
34                 }
35             }
36         }
37         System.out.println(islandNum);
38         System.out.println(lakeNum);
39 
40     }
41 
42     private static void dfs(int[][] island, int color, int x, int y) {
43         int m = island.length, n = island[0].length;
44         island[x][y] = color;
45         int newX, newY;
46         for (int i = 0; i < 4; i++) {
47             newX = x + directions[i][0];
48             newY = y + directions[i][1];
49             if (newX < 0 || newX >= m || newY < 0 || newY >= n)
50                 continue;
51             if (island[newX][newY] != 1)
52                 continue;
53             dfs(island, color, newX, newY);
54         }
55     }
56 
57     private static boolean dfs2(int[][] island, int surround, int x, int y) {
58         int m = island.length, n = island[0].length;
59         island[x][y] = -1;
60         int newX, newY;
61         for (int i = 0; i < 4; i++) {
62             newX = x + directions[i][0];
63             newY = y + directions[i][1];
64             if (newX < 0 || newX >= m || newY < 0 || newY >= n)
65                 continue;
66             int color = island[newX][newY];
67             if (color == -1)
68                 continue;
69             if (color != 0) {
70                 // This point is earth
71                 if (surround == -2) {
72                     surround = color;
73                 } else if (surround != color) {
74                     return false;
75                 }
76             } else {
77                 if (!dfs2(island, surround, newX, newY))
78                     return false;
79             }
80 
81         }
82         return true;
83     }
84 }