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 number16         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 earth71                 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 }