代碼隨想錄算法訓練營第五十二天 |101. 孤島的總面積102. 沉沒孤島103. 水流問題104.建造最大島嶼

101. 孤島的總面積

卡碼網：101. 孤島的總面積(opens new window)

題目描述

給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼指的是由水平或垂直方向上相鄰的陸地單元格組成的區域，且完全被水域單元格包圍。孤島是那些位于矩陣內部、所有單元格都不接觸邊緣的島嶼。

現在你需要計算所有孤島的總面積，島嶼面積的計算方式為組成島嶼的陸地的總數。

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0。

輸出描述

輸出一個整數，表示所有孤島的總面積，如果不存在孤島，則輸出 0。

輸入示例

輸出示例：

提示信息：

在矩陣中心部分的島嶼，因為沒有任何一個單元格接觸到矩陣邊緣，所以該島嶼屬于孤島，總面積為 1。

數據范圍：

1 <= M, N <= 50。

本題使用dfs，bfs，并查集都是可以的。

本題要求找到不靠邊的陸地面積，那么我們只要從周邊找到陸地然后通過 dfs或者bfs 將周邊靠陸地且相鄰的陸地都變成海洋，然后再去重新遍歷地圖統計此時還剩下的陸地就可以了。

如圖，在遍歷地圖周圍四個邊，靠地圖四邊的陸地，都為綠色，

在遇到地圖周邊陸地的時候，將1都變為0，此時地圖為這樣：

import java.util.*;public class Main {private static int count = 0;private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個方向private static void bfs(int[][] grid, int x, int y) {Queue<int[]> que = new LinkedList<>();que.add(new int[]{x, y});grid[x][y] = 0; // 只要加入隊列，立刻標記count++;while (!que.isEmpty()) {int[] cur = que.poll();int curx = cur[0];int cury = cur[1];for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了，直接跳過if (grid[nextx][nexty] == 1) {que.add(new int[]{nextx, nexty});count++;grid[nextx][nexty] = 0; // 只要加入隊列立刻標記}}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];// 讀取網格for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}// 從左側邊，和右側邊向中間遍歷for (int i = 0; i < n; i++) {if (grid[i][0] == 1) bfs(grid, i, 0);if (grid[i][m - 1] == 1) bfs(grid, i, m - 1);}// 從上邊和下邊向中間遍歷for (int j = 0; j < m; j++) {if (grid[0][j] == 1) bfs(grid, 0, j);if (grid[n - 1][j] == 1) bfs(grid, n - 1, j);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) bfs(grid, i, j);}}System.out.println(count);}
}

102. 沉沒孤島

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

現在你需要將所有孤島“沉沒”，即將孤島中的所有陸地單元格（1）轉變為水域單元格（0）。

輸入描述：

第一行包含兩個整數 N, M，表示矩陣的行數和列數。

之后 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述

輸出將孤島“沉沒”之后的島嶼矩陣。

輸入示例：

輸出示例：

提示信息：

將孤島沉沒：

數據范圍：

1 <= M, N <= 50

步驟一：深搜或者廣搜將地圖周邊的 1 （陸地）全部改成 2 （特殊標記）

步驟二：將水域中間 1 （陸地）全部改成水域（0）

步驟三：將之前標記的 2 改為 1 （陸地）

如圖：

import java.util.Scanner;public class Main {static int[][] dir = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; // 保存四個方向public static void dfs(int[][] grid, int x, int y) {grid[x][y] = 2;for (int[] d : dir) {int nextX = x + d[0];int nextY = y + d[1];// 超過邊界if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;// 不符合條件，不繼續遍歷if (grid[nextX][nextY] == 0 || grid[nextX][nextY] == 2) continue;dfs(grid, nextX, nextY);}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = scanner.nextInt();}}// 步驟一：// 從左側邊，和右側邊 向中間遍歷for (int i = 0; i < n; i++) {if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}// 從上邊和下邊 向中間遍歷for (int j = 0; j < m; j++) {if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}// 步驟二、步驟三for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) grid[i][j] = 0;if (grid[i][j] == 2) grid[i][j] = 1;}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {System.out.print(grid[i][j] + " ");}System.out.println();}scanner.close();}
}

103. 水流問題

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

現有一個 N × M 的矩陣，每個單元格包含一個數值，這個數值代表該位置的相對高度。矩陣的左邊界和上邊界被認為是第一組邊界，而矩陣的右邊界和下邊界被視為第二組邊界。

矩陣模擬了一個地形，當雨水落在上面時，水會根據地形的傾斜向低處流動，但只能從較高或等高的地點流向較低或等高并且相鄰（上下左右方向）的地點。我們的目標是確定那些單元格，從這些單元格出發的水可以達到第一組邊界和第二組邊界。

輸入描述：

第一行包含兩個整數 N 和 M，分別表示矩陣的行數和列數。

后續 N 行，每行包含 M 個整數，表示矩陣中的每個單元格的高度。

輸出描述：

輸出共有多行，每行輸出兩個整數，用一個空格隔開，表示可達第一組邊界和第二組邊界的單元格的坐標，輸出順序任意。

輸入示例：

1
2
3
4
5
6

輸出示例：

1
2
3
4
5
6
7
8

提示信息：

圖中的藍色方塊上的雨水既能流向第一組邊界，也能流向第二組邊界。所以最終答案為所有藍色方塊的坐標。

數據范圍：

1 <= M, N <= 50

public class Main {// 采用 DFS 進行搜索public static void dfs(int[][] heights, int x, int y, boolean[][] visited, int preH) {// 遇到邊界或者訪問過的點，直接返回if (x < 0 || x >= heights.length || y < 0 || y >= heights[0].length || visited[x][y]) return;// 不滿足水流入條件的直接返回if (heights[x][y] < preH) return;// 滿足條件，設置為true，表示可以從邊界到達此位置visited[x][y] = true;// 向下一層繼續搜索dfs(heights, x + 1, y, visited, heights[x][y]);dfs(heights, x - 1, y, visited, heights[x][y]);dfs(heights, x, y + 1, visited, heights[x][y]);dfs(heights, x, y - 1, visited, heights[x][y]);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] heights = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {heights[i][j] = sc.nextInt();}}// 初始化兩個二位boolean數組，代表兩個邊界boolean[][] pacific = new boolean[m][n];boolean[][] atlantic = new boolean[m][n];// 從左右邊界出發進行DFSfor (int i = 0; i < m; i++) {dfs(heights, i, 0, pacific, Integer.MIN_VALUE);dfs(heights, i, n - 1, atlantic, Integer.MIN_VALUE);}// 從上下邊界出發進行DFSfor (int j = 0; j < n; j++) {dfs(heights, 0, j, pacific, Integer.MIN_VALUE);dfs(heights, m - 1, j, atlantic, Integer.MIN_VALUE);}// 當兩個邊界二維數組在某個位置都為true時，符合題目要求List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (pacific[i][j] && atlantic[i][j]) {res.add(Arrays.asList(i, j));}}}// 打印結果for (List<Integer> list : res) {for (int k = 0; k < list.size(); k++) {if (k == 0) {System.out.print(list.get(k) + " ");} else {System.out.print(list.get(k));}}System.out.println();}}
}

104.建造最大島嶼

卡碼網題目鏈接（ACM模式）(opens new window)

題目描述：

給定一個由 1（陸地）和 0（水）組成的矩陣，你最多可以將矩陣中的一格水變為一塊陸地，在執行了此操作之后，矩陣中最大的島嶼面積是多少。

島嶼面積的計算方式為組成島嶼的陸地的總數。島嶼是被水包圍，并且通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設矩陣外均被水包圍。

輸入描述：

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述：

輸出一個整數，表示最大的島嶼面積。

輸入示例：

1
2
3
4
5

輸出示例

提示信息

對于上面的案例，有兩個位置可將 0 變成 1，使得島嶼的面積最大，即 6。

數據范圍：

1 <= M, N <= 50。

其實每次深搜遍歷計算最大島嶼面積，我們都做了很多重復的工作。

只要用一次深搜把每個島嶼的面積記錄下來就好。

第一步：一次遍歷地圖，得出各個島嶼的面積，并做編號記錄。可以使用map記錄，key為島嶼編號，value為島嶼面積

第二步：再遍歷地圖，遍歷0的方格（因為要將0變成1），并統計該1（由0變成的1）周邊島嶼面積，將其相鄰面積相加在一起，遍歷所有 0 之后，就可以得出選一個0變成1 之后的最大面積。

拿如下地圖的島嶼情況來舉例：（1為陸地）

第一步，則遍歷地圖，并將島嶼的編號和面積都統計好，過程如圖所示：

public class Main {// 該方法采用 DFS// 定義全局變量// 記錄每次每個島嶼的面積static int count;// 對每個島嶼進行標記static int mark;// 定義二維數組表示四個方位static int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};// DFS 進行搜索，將每個島嶼標記為不同的數字public static void dfs(int[][] grid, int x, int y, boolean[][] visited) {// 當遇到邊界，直接returnif (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return;// 遇到已經訪問過的或者遇到海水，直接返回if (visited[x][y] || grid[x][y] == 0) return;visited[x][y] = true;count++;grid[x][y] = mark;// 繼續向下層搜索dfs(grid, x, y + 1, visited);dfs(grid, x, y - 1, visited);dfs(grid, x + 1, y, visited);dfs(grid, x - 1, y, visited);}public static void main (String[] args) {// 接收輸入Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}// 初始化mark變量，從2開始（區別于0水，1島嶼）mark = 2;// 定義二位boolean數組記錄該位置是否被訪問boolean[][] visited = new boolean[m][n];// 定義一個HashMap，記錄某片島嶼的標記號和面積HashMap<Integer, Integer> getSize = new HashMap<>();// 定義一個HashSet，用來判斷某一位置水四周是否存在不同標記編號的島嶼HashSet<Integer> set = new HashSet<>();// 定義一個boolean變量，看看DFS之后，是否全是島嶼boolean isAllIsland = true;// 遍歷二維數組進行DFS搜索，標記每片島嶼的編號，記錄對應的面積for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) isAllIsland = false;if (grid[i][j] == 1) {count = 0;dfs(grid, i, j, visited);getSize.put(mark, count);mark++;}}}int result = 0;if (isAllIsland) result =  m * n;// 對標記完的grid繼續遍歷，判斷每個水位置四周是否有島嶼，并記錄下四周不同相鄰島嶼面積之和// 每次計算完一個水位置周圍可能存在的島嶼面積之和，更新下result變量for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {set.clear();// 當前水位置變更為島嶼，所以初始化為1int curSize = 1;for (int[] dir : dirs) {int curRow = i + dir[0];int curCol = j + dir[1];if (curRow < 0 || curRow >= m || curCol < 0 || curCol >= n) continue;int curMark = grid[curRow][curCol];// 如果當前相鄰的島嶼已經遍歷過或者HashMap中不存在這個編號，繼續搜索if (set.contains(curMark) || !getSize.containsKey(curMark)) continue;set.add(curMark);curSize += getSize.get(curMark);}result = Math.max(result, curSize);}}}// 打印結果System.out.println(result);}
}