孤島的總面積
題目描述
給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼指的是由水平或垂直方向上相鄰的陸地單元格組成的區域，且完全被水域單元格包圍。孤島是那些位于矩陣內部、所有單元格都不接觸邊緣的島嶼。現在你需要計算所有孤島的總面積，島嶼面積的計算方式為組成島嶼的陸地的總數。
解題思路
- 標記邊緣島嶼：首先遍歷矩陣的邊緣，如果發現陸地（1），則使用深度優先搜索（DFS）標記整個島嶼，這些島嶼不是孤島。
- 計算孤島面積：再次遍歷矩陣，對于未被標記且是陸地的單元格，使用DFS計算其所在島嶼的面積，并將所有孤島的面積累加。
代碼實現
import java.util.*;public class Main {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();}}boolean[][] visited = new boolean[m][n];// 標記邊緣島嶼for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 1 && !visited[i][j]) {visited[i][j] = true;dfsMarkEdge(i, j, visited, grid);}}}int totalArea = 0;// 計算孤島總面積for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;totalArea += dfsCalculateArea(i, j, visited, grid);}}}System.out.println(totalArea); }private static final int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};// DFS標記邊緣島嶼public static void dfsMarkEdge(int x, int y, boolean[][] visited, int[][] grid) {for (int i = 0; i < 4; i++) {int nextX = x + directions[i][0];int nextY = y + directions[i][1];if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;dfsMarkEdge(nextX, nextY, visited, grid);}}}// DFS計算孤島面積public static int dfsCalculateArea(int x, int y, boolean[][] visited, int[][] grid) {int area = 1;for (int i = 0; i < 4; i++) {int nextX = x + directions[i][0];int nextY = y + directions[i][1];if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;area += dfsCalculateArea(nextX, nextY, visited, grid);}}return area;}
}
沉沒孤島
題目描述
給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼指的是由水平或垂直方向上相鄰的陸地單元格組成的區域，且完全被水域單元格包圍。孤島是那些位于矩陣內部、所有單元格都不接觸邊緣的島嶼。現在你需要將所有孤島“沉沒”，即將孤島中的所有陸地單元格（1）轉變為水域單元格（0）。
解題思路
- 標記邊緣島嶼：首先遍歷矩陣的邊緣，如果發現陸地（1），則使用深度優先搜索（DFS）標記整個島嶼，這些島嶼不是孤島。
- 沉沒孤島：再次遍歷矩陣，對于未被標記且是陸地的單元格，將其置為0，從而實現沉沒孤島。
代碼實現
import java.util.*;public class Main {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();}}boolean[][] visited = new boolean[m][n];// 標記邊緣島嶼for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 1 && !visited[i][j]) {visited[i][j] = true;dfsMarkEdge(i, j, visited, grid);}}}// 沉沒孤島for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {grid[i][j] = 0;}}}// 輸出結果矩陣for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {System.out.print(grid[i][j] + " ");}System.out.println();}sc.close(); }private static final int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};// DFS標記邊緣島嶼public static void dfsMarkEdge(int x, int y, boolean[][] visited, int[][] grid) {for (int i = 0; i < 4; i++) {int nextX = x + directions[i][0];int nextY = y + directions[i][1];if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;dfsMarkEdge(nextX, nextY, visited, grid);}}}
}
水流問題
題目描述
現有一個 N × M 的矩陣，每個單元格包含一個數值，這個數值代表該位置的相對高度。矩陣的左邊界和上邊界被認為是第一組邊界（太平洋），而矩陣的右邊界和下邊界被視為第二組邊界（大西洋）。當雨水落在上面時，水會根據地形的傾斜向低處流動，但只能從較高或等高的地點流向較低或等高并且相鄰（上下左右方向）的地點。我們的目標是確定那些單元格，從這些單元格出發的水可以達到第一組邊界和第二組邊界。
解題思路
- 雙邊界標記：分別從太平洋和大西洋的邊界出發，使用深度優先搜索（DFS）標記所有能夠流向對應邊界的單元格。
- 對于太平洋，遍歷矩陣的左邊界和上邊界，從這些邊界上的每個單元格開始 DFS，標記所有能流向太平洋的單元格。
- 對于大西洋，遍歷矩陣的右邊界和下邊界，從這些邊界上的每個單元格開始 DFS，標記所有能流向大西洋的單元格。
- 結果收集：遍歷整個矩陣，找出同時被太平洋和大西洋標記的單元格，這些單元格即為所求。
代碼實現
import java.util.*;public class Main {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();}}// 初始化兩個二維 boolean 數組，分別代表能流向太平洋和大西洋的單元格boolean[][] pacific = new boolean[m][n];boolean[][] atlantic = new boolean[m][n];// 從太平洋邊界出發進行 DFSfor (int i = 0; i < m; i++) {dfs(i, 0, pacific, grid, Integer.MIN_VALUE);}for (int j = 0; j < n; j++) {dfs(0, j, pacific, grid, Integer.MIN_VALUE);}// 從大西洋邊界出發進行 DFSfor (int i = 0; i < m; i++) {dfs(i, n - 1, atlantic, grid, Integer.MIN_VALUE);}for (int j = 0; j < n; j++) {dfs(m - 1, j, atlantic, grid, Integer.MIN_VALUE);}// 收集結果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();}sc.close(); }// DFS 函數，用于標記能流向指定邊界的所有單元格public static void dfs(int x, int y, boolean[][] valid, int[][] grid, int preH) {if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || valid[x][y]) return;if (grid[x][y] < preH) return;valid[x][y] = true;dfs(x + 1, y, valid, grid, grid[x][y]);dfs(x - 1, y, valid, grid, grid[x][y]);dfs(x, y + 1, valid, grid, grid[x][y]);dfs(x, y - 1, valid, grid, grid[x][y]);}
}
建造最大島嶼
題目描述
給定一個由 1（陸地）和 0（水）組成的矩陣，你最多可以將矩陣中的一格水變為一塊陸地，在執行了此操作之后，矩陣中最大的島嶼面積是多少。島嶼面積的計算方式為組成島嶼的陸地的總數。島嶼是被水包圍，并且通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設矩陣外均被水包圍。
解題思路
- 預處理島嶼：首先遍歷整個矩陣，使用深度優先搜索（DFS）標記每個島嶼，并記錄每個島嶼的面積。
- 模擬填海：對于每個水域單元格，模擬將其變為陸地，然后檢查其上下左右相鄰的島嶼，計算這些島嶼合并后的總面積（包括當前填海的單元格）。
- 結果計算：在所有可能的填海位置中，找到最大的島嶼面積。
代碼實現
import java.util.*;
import java.math.*;public class Main {private static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};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();}}boolean[][] visited = new boolean[m][n];int mapnum = 1;int size = 0;HashMap<Integer, Integer> sizeMap = new HashMap<>();boolean isAllIsland = true;// 預處理所有島嶼for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) isAllIsland = false;if (!visited[i][j] && grid[i][j] == 1) {visited[i][j] = true;grid[i][j] = mapnum;size = dfs(i, j, visited, grid, mapnum);sizeMap.put(mapnum, size);mapnum++;}}}int result = 0;HashSet<Integer> adjacentIslands = new HashSet<>();// 如果整個矩陣都是島嶼if (isAllIsland) {result = m * n;} else {// 遍歷每個水域單元格，模擬填海for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {adjacentIslands.clear();int currentSize = 1; // 當前填海的單元格本身算1for (int z = 0; z < 4; z++) {int nextX = i + dir[z][0];int nextY = j + dir[z][1];if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) continue;int neighborMark = grid[nextX][nextY];if (adjacentIslands.contains(neighborMark) || !sizeMap.containsKey(neighborMark)) continue;adjacentIslands.add(neighborMark);currentSize += sizeMap.get(neighborMark);}result = Math.max(currentSize, result);}}}}System.out.println(result);}// DFS 計算島嶼面積并標記public static int dfs(int x, int y, boolean[][] visited, int[][] grid, int mapnum) {int size = 1;for (int i = 0; i < 4; i++) {int nextX = x + dir[i][0];int nextY = y + dir[i][1];if (nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length) continue;if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {visited[nextX][nextY] = true;grid[nextX][nextY] = mapnum;size += dfs(nextX, nextY, visited, grid, mapnum);}}return size;}
}
)
)
