Code Practice Journal | Day52_Graph03

本文主要是介绍Code Practice Journal | Day52_Graph03，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

KamaCoder 101. 孤岛的总面积

题目：101. 孤岛的总面积 (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

namespace ACMModeExample
{class Program{static void Main(string[] args){// 读取矩阵的行数和列数string[] dimensions = Console.ReadLine().Split();int N = int.Parse(dimensions[0]);int M = int.Parse(dimensions[1]);// 初始化矩阵int[,] grid = new int[N, M];// 读取矩阵数据for (int i = 0; i < N; i++){string[] line = Console.ReadLine().Split();for (int j = 0; j < M; j++){grid[i, j] = int.Parse(line[j]);}}// 标记数组，用于标记已访问的陆地bool[,] visited = new bool[N, M];int totalArea = 0;// 定义四个方向，分别是上、下、左、右int[] dRow = new int[] { -1, 1, 0, 0 };int[] dCol = new int[] { 0, 0, -1, 1 };// 检查是否在边界内bool IsWithinBoundary(int row, int col){return row >= 0 && row < N && col >= 0 && col < M;}// 深度优先搜索，计算岛屿的面积，同时判断是否为孤岛int Dfs(int row, int col, ref bool isIsolated){if (!IsWithinBoundary(row, col) || visited[row, col] || grid[row, col] == 0)return 0;visited[row, col] = true;int area = 1;// 如果任何陆地单元格接触了边界，标记为非孤岛if (row == 0 || row == N - 1 || col == 0 || col == M - 1){isIsolated = false;}for (int i = 0; i < 4; i++){int newRow = row + dRow[i];int newCol = col + dCol[i];area += Dfs(newRow, newCol, ref isIsolated);}return area;}// 遍历矩阵，查找所有岛屿for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){if (grid[i, j] == 1 && !visited[i, j]){bool isIsolated = true;int area = Dfs(i, j, ref isIsolated);if (isIsolated){totalArea += area;}}}}// 输出所有孤岛的总面积Console.WriteLine(totalArea);}}
}

summary

KamaCoder 102. 沉没孤岛

题目：102. 沉没孤岛 (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

namespace ACMModeExample
{class Program{static int[,] directions = new int[,]{{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }};static void Main(string[] args){// 读取第一行，包含两个整数 N 和 Mstring[] dimensions = Console.ReadLine().Split();int N = int.Parse(dimensions[0]);int M = int.Parse(dimensions[1]);int[,] matrix = new int[N, M];// 读取接下来的 N 行，每行包含 M 个整数for (int i = 0; i < N; i++){string[] rows = Console.ReadLine().Split();for (int j = 0; j < M; j++){matrix[i, j] = int.Parse(rows[j]);}}// 处理边界，将边界上的岛屿及其相连的岛屿标记为非孤岛for (int i = 0; i < N; i++){if (matrix[i, 0] == 1)MarkNonIsolated(matrix, i, 0, N, M);if (matrix[i, M - 1] == 1)MarkNonIsolated(matrix, i, M - 1, N, M);}for (int j = 0; j < M; j++){if (matrix[0, j] == 1)MarkNonIsolated(matrix, 0, j, N, M);if (matrix[N - 1, j] == 1)MarkNonIsolated(matrix, N - 1, j, N, M);}// 处理矩阵内部，将孤岛沉没for (int i = 1; i < N - 1; i++){for (int j = 1; j < M - 1; j++){if (matrix[i, j] == 1){matrix[i, j] = 0;  // 沉没孤岛}}}// 恢复标记为-1的边界岛屿for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){if (matrix[i, j] == -1){matrix[i, j] = 1;}}}// 输出沉没孤岛后的矩阵for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){Console.Write(matrix[i, j] + " ");}Console.WriteLine();}}static void MarkNonIsolated(int[,] matrix, int x, int y, int N, int M){matrix[x, y] = -1;  // 标记为非孤岛for (int i = 0; i < 4; i++){int newX = x + directions[i, 0];int newY = y + directions[i, 1];if (newX >= 0 && newX < N && newY >= 0 && newY < M && matrix[newX, newY] == 1){MarkNonIsolated(matrix, newX, newY, N, M);}}}}
}

summary

KamaCoder 103. 水流问题

题目：103. 水流问题 (kamacoder.com)
​​​​​​​题解：代码随想录 (programmercarl.com)

solution

namespace ACMModeExample
{class Program{static void Main(string[] args){// 读取矩阵的尺寸string[] dimensions = Console.ReadLine().Split();int N = int.Parse(dimensions[0]);int M = int.Parse(dimensions[1]);// 初始化矩阵int[,] heights = new int[N, M];for (int i = 0; i < N; i++){string[] row = Console.ReadLine().Split();for (int j = 0; j < M; j++){heights[i, j] = int.Parse(row[j]);}}// 初始化两个布尔矩阵，用于标记是否可以到达第一组边界和第二组边界bool[,] canReachFirstBoundary = new bool[N, M];bool[,] canReachSecondBoundary = new bool[N, M];// 从第一组边界开始 DFS：包括左边界和上边界for (int i = 0; i < N; i++){DFS(heights, canReachFirstBoundary, i, 0);}for (int j = 0; j < M; j++){DFS(heights, canReachFirstBoundary, 0, j);}// 从第二组边界开始 DFS：包括右边界和下边界for (int i = 0; i < N; i++){DFS(heights, canReachSecondBoundary, i, M - 1);}for (int j = 0; j < M; j++){DFS(heights, canReachSecondBoundary, N - 1, j);}// 输出结果：找出同时可以到达两组边界的单元格for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){if (canReachFirstBoundary[i, j] && canReachSecondBoundary[i, j]){Console.WriteLine($"{i} {j}");}}}}// 深度优先搜索 (DFS)private static void DFS(int[,] heights, bool[,] canReach, int x, int y){if (canReach[x, y]) return;canReach[x, y] = true;// 向四个方向探索（上、下、左、右）if (x > 0 && heights[x - 1, y] >= heights[x, y]){DFS(heights, canReach, x - 1, y); // 向上}if (x < heights.GetLength(0) - 1 && heights[x + 1, y] >= heights[x, y]){DFS(heights, canReach, x + 1, y); // 向下}if (y > 0 && heights[x, y - 1] >= heights[x, y]){DFS(heights, canReach, x, y - 1); // 向左}if (y < heights.GetLength(1) - 1 && heights[x, y + 1] >= heights[x, y]){DFS(heights, canReach, x, y + 1); // 向右}}}
}

summary

这篇关于Code Practice Journal | Day52_Graph03的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---