代码随想录算法训练营第五十一天|Day51 图论

岛屿数量 深搜

https://www.programmercarl.com/kamacoder/0099.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%95%B0%E9%87%8F%E6%B7%B1%E6%90%9C.html

思路

#include <stdio.h>
#define MAX_SIZE 50
int grid[MAX_SIZE][MAX_SIZE]; 
int visited[MAX_SIZE][MAX_SIZE]; 
int N, M; 
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void DFS(int x, int y) {visited[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 && grid[newX][newY] == 1 && !visited[newX][newY]) {DFS(newX, newY);}}
}
int main() {scanf("%d %d", &N, &M);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {scanf("%d", &grid[i][j]);visited[i][j] = 0; }}int islandCount = 0; for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == 1 && !visited[i][j]) {DFS(i, j); islandCount++; }}}printf("%d\n", islandCount);return 0;
}

学习反思

用深度优先搜索算法(Depth-First Search, DFS)求解岛屿数量的程序。代码使用一个二维数组grid来表示一个由0和1组成的地图，其中1表示陆地，0表示水。代码中的visited数组用于记录每个格子是否被访问过。主要的算法逻辑在DFS函数中实现。DFS函数会将当前格子标记为已访问，然后递归地对当前格子的上、下、左、右四个邻居格子进行访问，如果邻居格子满足一些条件（在地图范围内且为1且未被访问过），则继续递归访问邻居格子。通过递归的方式，DFS函数可以遍历到所有与当前格子相连的陆地格子。在主函数中，首先读取地图的行数N和列数M。然后使用两个嵌套循环遍历地图中的所有格子，并读取每个格子的值并初始化visited数组。接下来，使用两个嵌套循环遍历地图中的所有格子。如果发现一个未访问过的陆地格子，就调用DFS函数进行访问，并将岛屿数量加1。最后，输出岛屿数量。这段代码的时间复杂度为O(NM)，其中N和M分别为地图的行数和列数。代码中使用了递归，递归深度最大为NM，空间复杂度为O(N*M)。

岛屿数量 广搜

https://www.programmercarl.com/kamacoder/0099.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%95%B0%E9%87%8F%E5%B9%BF%E6%90%9C.html

思路

#include <stdio.h>#define MAX 50int grid[MAX][MAX];
int visited[MAX][MAX];
int n, m;
int directions[4][2] = {{-1, 0},  // 上{1, 0},   // 下{0, -1},  // 左{0, 1}    // 右
};
void dfs(int x, int y) {visited[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 && grid[newX][newY] == 1 && visited[newX][newY] == 0) {dfs(newX, newY);}}
}int main() {scanf("%d %d", &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &grid[i][j]);visited[i][j] = 0; }}int islandCount = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1 && visited[i][j] == 0) {dfs(i, j); islandCount++; }}}printf("%d\n", islandCount);return 0;
}

学习反思

用深度优先搜索算法（DFS）来解决岛屿数量的问题。代码将二维数组grid用于表示地图，其中1表示陆地，0表示水。visited数组用于标记格子是否被访问过。主要的算法逻辑在dfs函数中实现。dfs函数会将当前格子标记为已访问，然后递归地访问当前格子的上、下、左、右四个邻居格子。如果邻居格子满足一些条件（在地图范围内且为1且未被访问过），则继续递归地访问邻居格子。通过递归的方式，dfs函数可以遍历到所有与当前格子相连的陆地格子。在主函数中，首先读取地图的行数n和列数m。然后使用两个嵌套循环遍历地图中的所有格子，并读取每个格子的值并初始化visited数组。接下来，使用两个嵌套循环遍历地图中的所有格子。如果发现一个未访问过的陆地格子，就调用dfs函数进行访问，并将岛屿数量加1。最后，输出岛屿数量。这段代码的时间复杂度为O(nm)，其中n和m分别为地图的行数和列数。代码中使用了递归，递归深度最大为nm，空间复杂度为O(n*m)。

岛屿的最大面积

https://www.programmercarl.com/kamacoder/0100.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF.html

思路

#include <stdio.h>#define MAX_N 50
#define MAX_M 50int grid[MAX_N][MAX_M];
int visited[MAX_N][MAX_M];
int N, M;
int directions[4][2] = {{0, 1},   // right{1, 0},   // down{0, -1},  // left{-1, 0}   // up
};
int is_valid(int x, int y) {return x >= 0 && x < N && y >= 0 && y < M && grid[x][y] == 1 && !visited[x][y];
}
int dfs(int x, int y) {visited[x][y] = 1;int area = 1;for (int i = 0; i < 4; i++) {int new_x = x + directions[i][0];int new_y = y + directions[i][1];if (is_valid(new_x, new_y)) {area += dfs(new_x, new_y);}}return area;
}
int main() {scanf("%d %d", &N, &M);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {scanf("%d", &grid[i][j]);visited[i][j] = 0; }}int max_area = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {// If we find a land cell that hasn't been visited yetif (grid[i][j] == 1 && !visited[i][j]) {int area = dfs(i, j);if (area > max_area) {max_area = area;}}}}  printf("%d\n", max_area);return 0;
}

学习反思

使用深度优先搜索算法（DFS）来计算最大岛屿面积。首先，定义了最大行数N和最大列数M，并声明了地图数组grid和访问数组visited。is_valid函数用于判断一个格子是否有效，即格子的坐标在合法范围内，且为陆地（值为1），且未被访问过。dfs函数用于进行深度优先搜索。它首先将当前格子标记为已访问，并初始化面积为1。然后，遍历当前格子的四个方向的邻居格子，如果邻居格子有效，则递归调用dfs函数，并将返回的面积加到当前面积上。最后，返回当前面积。在主函数中，首先读取地图的行数N和列数M。然后，使用两个嵌套循环遍历地图中的所有格子，并读取每个格子的值并初始化visited数组。接下来，使用两个嵌套循环遍历地图中的所有格子。如果发现一个未访问过的陆地格子，就调用dfs函数进行深度优先搜索，并将返回的面积与最大面积进行比较，更新最大面积。最后，输出最大面积。这段代码的时间复杂度为O(NM)，其中N和M分别为地图的行数和列数。代码中使用了递归，递归深度最大为NM，空间复杂度为O(N*M)。为了提高效率，使用了is_valid函数来判断格子的有效性，避免了不必要的访问和递归调用。