孤岛的总面积
题目描述
给定一个由 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];
// 从太平洋边界出发进行 DFS
for (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);
}
// 从大西洋边界出发进行 DFS
for (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; // 当前填海的单元格本身算1
for (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;
}
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
