[KamaCoder] 100. 岛屿的最大面积
[KamaCoder] 100. 岛屿的最大面积 文章解释
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。
输入示例
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例
4样例输入中，岛屿的最大面积为 4。
数据范围：
1 <= M, N <= 50。
[KamaCoder] 100. 岛屿的最大面积
自己看到题目的第一想法
深搜一下, 每次遇到没有访问过的陆地, 就把面积加 1, 同时继续遍历与该节点相邻的陆地, 将相邻陆地的面积累加到当前陆地上, 并返回给上一级陆地, 最终完成统计.
看完代码随想录之后的想法
基本上是类似的.
import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
while (scanner.hasNext()) {
int rowCount = scanner.nextInt();
int columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
int result = 0;
for (int x = 0; x < nodes.length; x++) {
for (int y = 0; y < nodes[x].length; y++) {
if (visited[x][y] || nodes[x][y] != 1) {
continue;
}
visited[x][y] = true;
result = Math.max(result, dfs(nodes, visited, x, y));
}
}
System.out.println(result);
}
private static int dfs(int[][] nodes, boolean visited[][], int x, int y) {
int newX;
int newY;
int result = 1;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (visited[newX][newY] || nodes[newX][newY] != 1) {
continue;
}
visited[newX][newY] = true;
result += dfs(nodes, visited, newX, newY);
}
return result;
}
}// for 循环清爽版
import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
while (scanner.hasNext()) {
int rowCount = scanner.nextInt();
int columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
int result = 0;
for (int x = 0; x < nodes.length; x++) {
for (int y = 0; y < nodes[x].length; y++) {
// 这里变得简单一些
result = Math.max(result, dfs(nodes, visited, x, y));
}
}
System.out.println(result);
}
private static int dfs(int[][] nodes, boolean visited[][], int x, int y) {
// 判断都已到下面两个 if 里了, 同时每次会多一些递归调用.
if (x < 0 || x >= nodes.length || y < 0 || y >= nodes[x].length) {
return 0;
}
if (visited[x][y] || nodes[x][y] != 1) {
return 0;
}
visited[x][y] = true;
int newX;
int newY;
int result = 1;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
// 这里变得简单一些
result += dfs(nodes, visited, newX, newY);
}
return result;
}
}import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;
// bfs 版本
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
while (scanner.hasNext()) {
int rowCount = scanner.nextInt();
int columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
int result = 0;
for (int x = 0; x < nodes.length; x++) {
for (int y = 0; y < nodes[x].length; y++) {
// 这里变得简单一些
result = Math.max(result, bfs(nodes, visited, x, y));
}
}
System.out.println(result);
}
private static int bfs(int[][] nodes, boolean visited[][], int x, int y) {
if (x < 0 || x >= nodes.length || y < 0 || y >= nodes[x].length) {
return 0;
}
if (visited[x][y] || nodes[x][y] != 1) {
return 0;
}
Deque<Integer> toNodes = new LinkedList<>();
toNodes.addLast(x);
toNodes.addLast(y);
visited[x][y] = true;
int result = 0;
while (!toNodes.isEmpty()) {
x = toNodes.pop();
y = toNodes.pop();
result++;
int newX;
int newY;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
// 这里变得简单一些
// 判断都已到下面两个 if 里了, 同时每次会多一些递归调用.
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (visited[newX][newY] || nodes[newX][newY] != 1) {
continue;
}
toNodes.addLast(newX);
toNodes.addLast(newY);
visited[newX][newY] = true;
}
}
return result;
}
}自己实现过程中遇到哪些困难
hhh, 卡神说你不要 pop 了再更新 visited 数组, 不然节点会重复计算... 小心翼翼之后, 还是在某天过后忘记了~ 还好一下子就意识到问题所在, 排查起来也快.
[KamaCoder] 101. 孤岛的总面积
[KamaCoder] 101. 孤岛的总面积 文章解释
[KamaCoder] 101. 孤岛的总面积
自己看到题目的第一想法
dfs 它! 如果当前遇到了边缘节点, 则面积返回0. 上层节点发现下层递归返回面积为 0, 则知道当前遇到了边缘, 这时候需要继续递归其他子节点做上标记, 同时记录住当前岛屿非孤岛.
import java.util.Scanner;
// 容易超时版本
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
while (scanner.hasNext()) {
int rowCount = scanner.nextInt();
int columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
int result = 0;
for (int i = 0; i < nodes.length; i++) {
for (int j = 0; j < nodes[i].length; j++) {
if (visited[i][j] || nodes[i][j] != 1) {
continue;
}
result += dfs(nodes, visited, i, j);
}
}
System.out.println(result);
}
private static int dfs(int[][] nodes, boolean[][] visited, int x, int y) {
visited[x][y] = true;
int result = 0;
int newX;
int newY;
boolean isNotLonelyIsland = false;// 没有什么是一个变量处理不了的
if (x == 0 || x == nodes.length - 1 || y == 0 || y == nodes[x].length - 1) {
isNotLonelyIsland = true;
}
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (visited[newX][newY] || nodes[newX][newY] != 1) {
continue;
}
int childResult = dfs(nodes, visited, newX, newY);
if (childResult == 0) {// 如果不行就两个...
isNotLonelyIsland = true;
}
result += childResult;
}
if (isNotLonelyIsland) {
return 0;
}
return result + 1;
}
}import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;
// bfs 版本: 第一次必超时版本.
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
while (scanner.hasNext()) {
int rowCount = scanner.nextInt();
int columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
int result = 0;
for (int i = 0; i < nodes.length; i++) {
for (int j = 0; j < nodes[i].length; j++) {
result += bfs(nodes, visited, i, j);
}
}
System.out.println(result);
}
private static int bfs(int[][] nodes, boolean[][] visited, int x, int y) {
if (x < 0 || x >= nodes.length || y < 0 || y >= nodes[x].length) {
return 0;
}
if (visited[x][y] || nodes[x][y] != 1) {
return 0;
}
Deque<Integer> childNodes = new LinkedList<>();
childNodes.addLast(x);
childNodes.addLast(y);
visited[x][y] = true;
int result = 0;
boolean isNotLonelyIsland = false;
if (x == 0 || x == nodes.length - 1 || y == 0 || y == nodes[x].length - 1) {
isNotLonelyIsland = true;
}
while (!childNodes.isEmpty()) {
x = childNodes.pop();
y = childNodes.pop();
int newX;
int newY;
result++;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (visited[newX][newY] || nodes[newX][newY] != 1) {
continue;
}
if (newX == 0 || newX == nodes.length - 1 || newY == 0 || newY == nodes[newX].length - 1) {
isNotLonelyIsland = true;
}
childNodes.addLast(newX);
childNodes.addLast(newY);
visited[newX][newY] = true;
}
}
return isNotLonelyIsland ? 0 : result;
}
}
看完代码随想录之后的想法
先沉没所有的非孤岛, 再计算孤岛, great!
import java.util.Scanner;
// 稳定超时版本~
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
int rowCount = 0;
int columnCount = 0;
while (scanner.hasNext()) {
rowCount = scanner.nextInt();
columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
for (int i = 0; i < rowCount; i++) {
if (nodes[i][0] == 1) {
dfs(nodes, i, 0);
}
if (nodes[i][columnCount - 1] == 1) {
dfs(nodes, i, columnCount - 1);
}
}
for (int i = 0; i < columnCount; i++) {
if (nodes[0][i] == 1) {
dfs(nodes, 0, i);
}
if (nodes[rowCount - 1][i] == 1) {
dfs(nodes, rowCount - 1, i);
}
}
int result = 0;
for (int i = 0; i < nodes.length; i++) {
for (int j = 0; j < nodes[i].length; j++) {
if (nodes[i][j] != 1) {
continue;
}
result += dfs(nodes, i, j);
}
}
System.out.println(result);
}
private static int dfs(int[][] nodes, int x, int y) {
if (nodes[x][y] != 1) {
return 0;
}
int result = 1;
int newX;
int newY;
nodes[x][y] = 0;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (nodes[newX][newY] != 1) {
continue;
}
result += dfs(nodes, newX, newY);
}
return result;
}
}import java.util.Scanner;
// 有概率超时
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private static int result = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
int rowCount = 0;
int columnCount = 0;
while (scanner.hasNext()) {
rowCount = scanner.nextInt();
columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
for (int i = 0; i < rowCount; i++) {
if (nodes[i][0] == 1) {
dfs(nodes, i, 0);
}
if (nodes[i][columnCount - 1] == 1) {
dfs(nodes, i, columnCount - 1);
}
}
for (int i = 0; i < columnCount; i++) {
if (nodes[0][i] == 1) {
dfs(nodes, 0, i);
}
if (nodes[rowCount - 1][i] == 1) {
dfs(nodes, rowCount - 1, i);
}
}
result = 0;
for (int i = 0; i < nodes.length; i++) {
for (int j = 0; j < nodes[i].length; j++) {
if (nodes[i][j] != 1) {
continue;
}
dfs(nodes, i, j);
}
}
System.out.println(result);
}
// 不要返回值才能通过T_T
private static void dfs(int[][] nodes, int x, int y) {
int newX;
int newY;
nodes[x][y] = 0;
result++;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (nodes[newX][newY] != 1) {
continue;
}
dfs(nodes, newX, newY);
}
return;
}
}自己实现过程中遇到哪些困难
超时了~
[KamaCoder] 102. 沉没孤岛
[KamaCoder] 102. 沉没孤岛 文章解释
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。
之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出将孤岛“沉没”之后的岛屿矩阵。 注意：每个元素后面都有一个空格
输入示例
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1提示信息
将孤岛沉没。
数据范围：
1 <= M, N <= 50。
[KamaCoder] 102. 沉没孤岛
自己看到题目的第一想法
和孤岛总面积一样, 先标记一一下边缘陆地, 再把非边缘陆地变为水. 这样的话需要二维数组 visited[][] 以及 boolean needSink 来辅助判断是否需要沉没当前节点.
看完代码随想录之后的想法
将边缘陆地修改为2, 沉没为1的孤岛, 重置边缘陆地为1. Great!
确实没有想着去复用数据~
import java.util.Scanner;
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
int rowCount = 0;
int columnCount = 0;
while (scanner.hasNext()) {
rowCount = scanner.nextInt();
columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
for (int i = 0; i < rowCount; i++) {
if (nodes[i][0] == 1) {
dfs(nodes, i, 0);
}
if (nodes[i][columnCount - 1] == 1) {
dfs(nodes, i, columnCount - 1);
}
}
for (int i = 0; i < columnCount; i++) {
if (nodes[0][i] == 1) {
dfs(nodes, 0, i);
}
if (nodes[rowCount - 1][i] == 1) {
dfs(nodes, rowCount - 1, i);
}
}
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
if (nodes[i][j] == 1) {
nodes[i][j] = 0;
}
if (nodes[i][j] == 2) {
nodes[i][j] = 1;
}
if (j != columnCount - 1) {
System.out.print(nodes[i][j] + " ");
} else {
System.out.println(nodes[i][j]);
}
}
}
}
private static void dfs(int[][] nodes, int x, int y) {
nodes[x][y] = 2;
int newX;
int newY;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (nodes[newX][newY] == 2 || nodes[newX][newY] == 0) {
continue;
}
dfs(nodes, newX, newY);
}
}
}自己实现过程中遇到哪些困难
无.
[KamaCoder] 103. 水流问题
[KamaCoder] 103. 水流问题 文章解释
题目描述
现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。
输入描述
第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。
后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。
输出描述
输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。
输入示例
5 5 1 3 1 2 4 1 2 1 3 2 2 4 7 2 1 4 5 6 1 1 1 4 1 2 1输出示例
0 4 1 3 2 2 3 0 3 1 3 2 4 0 4 1数据范围：
1 <= M, N <= 100。
[KamaCoder] 103. 水流问题
自己看到题目的第一想法
要怎么才能找到高点呢? 毫无头绪
看完代码随想录之后的想法
逆流而上! 爬不动的时候停止. 如果从两个方向逆流而上都能到达的节点, 水就能从这个节点留到两个方向去.
import java.util.Scanner;
// 不知道还能怎么剪枝了, 永远的超时~
public class Main {
private static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] nodes = null;
boolean[][] visited = null;
int rowCount = 0;
int columnCount = 0;
while (scanner.hasNext()) {
rowCount = scanner.nextInt();
columnCount = scanner.nextInt();
nodes = new int[rowCount][columnCount];
visited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
nodes[i][j] = scanner.nextInt();
}
}
}
boolean[][] firstVisited = new boolean[rowCount][columnCount];
boolean[][] secondVisited = new boolean[rowCount][columnCount];
for (int i = 0; i < rowCount; i++) {
if (!firstVisited[i][0]) {
dfs(nodes, firstVisited, i, 0);
}
if (!secondVisited[i][columnCount - 1]) {
dfs(nodes, secondVisited, i, columnCount - 1);
}
}
for (int i = 0; i < columnCount; i++) {
if (!firstVisited[0][i]) {
dfs(nodes, firstVisited, 0, i);
}
if (!secondVisited[rowCount - 1][i]) {
dfs(nodes, secondVisited, rowCount - 1, i);
}
}
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
if (firstVisited[i][j] && secondVisited[i][j]) {
System.out.println(i + " " + j);
}
}
}
}
private static void dfs(int[][] nodes, boolean[][] visited, int x, int y) {
if (visited[x][y]) {
return;
}
visited[x][y] = true;
int newX;
int newY;
for (int i = 0; i < dir.length; i++) {
newX = x + dir[i][0];
newY = y + dir[i][1];
if (newX < 0 || newX >= nodes.length || newY < 0 || newY >= nodes[newX].length) {
continue;
}
if (visited[newX][newY] || nodes[x][y] > nodes[newX][newY]) {
continue;
}
dfs(nodes, visited, newX, newY);
}
}
}自己实现过程中遇到哪些困难
超时了~ 没 AC~
![C语言力扣刷题7——删除排序链表中的重复元素 II——[快慢双指针法]](https://img-blog.csdnimg.cn/direct/0e5027c649f64de2b7a277ec335e35f5.png#pic_center)
![uniapp, [TypeError] “Failed to fetch dynamically imported module“ 报错解决思路](https://i-blog.csdnimg.cn/direct/c1e1641675824b858c1a64a5b583fbca.png#pic_center)
