Code Practice Journal | Day51__Graph02

LeetCode 200. 岛屿数量

题目：200. 岛屿数量 - 力扣（LeetCode）

solution

public class Solution {int result = 0;public int NumIslands(char[][] grid) {int m = grid.Length;int n = grid[0].Length;for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(grid[i][j] == '1'){islandTra(grid, i, j , m, n);result ++;}}}return result;}public void islandTra(char[][] grid, int x, int y, int m, int n){if(x < 0 || y < 0 || x >= m || y >= n) return;if(grid[x][y] == '0' || grid[x][y] == '2') return;grid[x][y] = '2';islandTra(grid, x, y + 1, m, n);islandTra(grid, x, y - 1, m, n);islandTra(grid, x + 1, y, m, n);islandTra(grid, x - 1, y, m, n);}
}

summary

两种遍历：

外层遍历grid所有元素，找到未被遍历过的岛屿——'1'

内层DFS岛屿所有元素，标记遍历过的岛屿——'2'

KamaCoder 99. 岛屿数量

题目：99. 岛屿数量 (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

class Program
{public static void Main(string[] args){// 处理输入//     读取第一行，拆分维度string[] first = Console.ReadLine().Split();int n = int.Parse(first[0]);int m = int.Parse(first[1]);//     构建01图int[,] graph = new int[n, m];for (int i = 0; i < n; i++){string[] line = Console.ReadLine().Split();for (int j = 0; j < m; j++){graph[i, j] = int.Parse(line[j]);}}int result = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (graph[i, j] == 1){result++;DFS(graph, i, j, n, m);}}}Console.WriteLine(result);}public static void DFS(int[,] graph, int i, int j, int n, int m){if (i < 0 || i >= n || j < 0 || j >= m) return;if (graph[i, j] == 2 || graph[i, j] == 0) return;graph[i, j] = 2;DFS(graph, i - 1, j, n, m);DFS(graph, i + 1, j, n, m);DFS(graph, i, j - 1, n, m);DFS(graph, i, j + 1, n, m);}
}

LeetCode 695. 岛屿的最大面积

 题目：695. 岛屿的最大面积 - 力扣（LeetCode）

在上题基础上加入当前面积和更新面积的操作

solution

public class Solution {int result = 0;int area = 0;public int MaxAreaOfIsland(int[][] grid) {int m = grid.Length;int n = grid[0].Length;for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(grid[i][j] == 1){area = 0;islandTra(grid, i, j , m, n);result = Math.Max(result, area);}}}return result;}public void islandTra(int[][] grid, int x, int y, int m, int n){if(x < 0 || y < 0 || x >= m || y >= n) return;if(grid[x][y] == 0 || grid[x][y] == 2) return;grid[x][y] = 2;area ++;islandTra(grid, x, y + 1, m, n);islandTra(grid, x, y - 1, m, n);islandTra(grid, x + 1, y, m, n);islandTra(grid, x - 1, y, m, n);}
}

KamaCoder 100. 岛屿的最大面积

题目：100. 岛屿的最大面积 (kamacoder.com)
题解：代码随想录 (programmercarl.com)

solution

using System;public class Program {public 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[] row = Console.ReadLine().Split();for (int j = 0; j < M; j++) {grid[i, j] = int.Parse(row[j]);}}// 计算最大岛屿面积int maxArea = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i, j] == 1) {// 每发现一个岛屿，计算其面积并更新最大面积int currentArea = DFS(grid, i, j, N, M);maxArea = Math.Max(maxArea, currentArea);}}}// 输出最大岛屿面积Console.WriteLine(maxArea);}// DFS 递归函数，用于计算岛屿面积private static int DFS(int[,] grid, int i, int j, int N, int M) {// 如果越界或当前格子是水（0），则返回面积0if (i < 0 || i >= N || j < 0 || j >= M || grid[i, j] == 0) {return 0;}// 将当前格子标记为已访问（0表示水）grid[i, j] = 0;// 计算当前格子的面积为1，并递归计算四个方向的面积int area = 1;area += DFS(grid, i - 1, j, N, M); // 上area += DFS(grid, i + 1, j, N, M); // 下area += DFS(grid, i, j - 1, N, M); // 左area += DFS(grid, i, j + 1, N, M); // 右return area;}
}