代码随想录算法训练营第五十二天|Day52 图论
孤岛的总面积
思路
#include <stdio.h>
#define MAX_N 50
#define MAX_M 50
int grid[MAX_N][MAX_M];
int visited[MAX_N][MAX_M];
int N, M;
int directions[4][2] = {
{0, 1}, // 右
{1, 0}, // 下
{0, -1}, // 左
{-1, 0} // 上
};
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 touches_boundary(int x, int y) {
return x == 0 || x == N - 1 || y == 0 || y == M - 1;
}
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 total_island_area = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
if (!touches_boundary(i, j)) {
int area = dfs(i, j);
total_island_area += area;
} else {
dfs(i, j);
}
}
}
}
printf("%d\n", total_island_area);
return 0;
}学习反思
实现了一个求解岛屿面积的功能。代码使用深度优先搜索（DFS）来遍历岛屿，并使用一个二维数组来记录哪些格子已经被访问过。在主函数中，首先读入岛屿的大小和格子的值，然后使用两层循环遍历岛屿的每个格子。如果当前格子是一个岛屿且未被访问过，就进行DFS遍历。DFS函数中，首先将当前格子标记为已访问，并初始化岛屿面积为1。然后依次遍历当前格子的上、下、左、右四个方向，如果某个方向的格子是一个合法的岛屿格子（即在岛屿范围内且未被访问过），就递归调用DFS函数，并将返回的面积累加到当前岛屿面积中。最后返回岛屿面积。代码中还定义了一个辅助函数touches_boundary，用来判断一个岛屿是否与岛屿边界相连。如果当前格子位于岛屿边界（即在第一行、最后一行、第一列或最后一列），那么该岛屿与边界相连，就不计入总岛屿面积中。在学习和反思方面，代码的逻辑清晰，实现了所需功能。但是在读取输入时未进行错误处理，如果输入的岛屿大小超过了定义的最大值，可能会导致程序出错。另外，在DFS函数中使用了递归，如果岛屿很大，可能会导致栈溢出。对于大规模的岛屿，可以考虑使用非递归的DFS或其他算法进行优化。
沉没孤岛
https://www.programmercarl.com/kamacoder/0102.%E6%B2%89%E6%B2%A1%E5%AD%A4%E5%B2%9B.html
思路
#include <stdio.h>
#define MAX_N 50
#define MAX_M 50
int grid[MAX_N][MAX_M];
int visited[MAX_N][MAX_M];
int N, M;
int directions[4][2] = {
{0, 1}, // 右
{1, 0}, // 下
{0, -1}, // 左
{-1, 0} // 上
};
int is_valid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M && grid[x][y] == 1 && !visited[x][y];
}
void dfs_mark_boundary(int x, int y) {
visited[x][y] = 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)) {
dfs_mark_boundary(new_x, new_y);
}
}
}
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;
}
}
for (int j = 0; j < M; j++) {
if (grid[0][j] == 1 && !visited[0][j]) {
dfs_mark_boundary(0, j);
}
if (grid[N-1][j] == 1 && !visited[N-1][j]) {
dfs_mark_boundary(N-1, j);
}
}
for (int i = 0; i < N; i++) {
if (grid[i][0] == 1 && !visited[i][0]) {
dfs_mark_boundary(i, 0);
}
if (grid[i][M-1] == 1 && !visited[i][M-1]) {
dfs_mark_boundary(i, M-1);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
grid[i][j] = 0;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
printf("%d ", grid[i][j]);
}
printf("\n");
}
return 0;
}学习反思
对原来的岛屿面积计算代码进行了修改，不再计算总岛屿面积，而是将与岛屿边界相连的岛屿格子标记为0，表示它们不属于岛屿的一部分。修改后的代码在主函数中，首先读入岛屿的大小和格子的值，然后使用两层循环遍历岛屿的每个格子，再使用两层循环遍历岛屿的边界格子。如果当前格子是一个岛屿且未被访问过，就进行DFS遍历，并将相连的岛屿格子标记为已访问。最后，再遍历一次岛屿格子数组，将未被访问过的岛屿格子标记为0。代码的逻辑清晰，实现了将与岛屿边界相连的岛屿格子标记为0的功能。但是代码中没有进行错误处理，如果输入的岛屿大小超过了定义的最大值，可能会导致程序出错。另外，在DFS函数中使用了递归，如果岛屿很大，可能会导致栈溢出。对于大规模的岛屿，可以考虑使用非递归的DFS或其他算法进行优化。
水流问题
https://www.programmercarl.com/kamacoder/0103.%E6%B0%B4%E6%B5%81%E9%97%AE%E9%A2%98.html
思路
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 100
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(int grid[MAX_N][MAX_M], bool visited[MAX_N][MAX_M], int x, int y) {
if (visited[x][y]) return;
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if (grid[x][y] > grid[nextx][nexty]) continue;
dfs(grid, visited, nextx, nexty);
}
}
int main() {
int grid[MAX_N][MAX_M];
bool firstBorder[MAX_N][MAX_M] = {false};
bool secondBorder[MAX_N][MAX_M] = {false};
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &grid[i][j]);
}
}
for (int i = 0; i < n; i++) {
dfs(grid, firstBorder, i, 0);
dfs(grid, secondBorder, i, m - 1);
}
for (int j = 0; j < m; j++) {
dfs(grid, firstBorder, 0, j);
dfs(grid, secondBorder, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (firstBorder[i][j] && secondBorder[i][j]) {
printf("%d %d\n", i, j);
}
}
}
return 0;
}学习反思
代码是一个基于深度优先搜索（DFS）的算法，用于找到一个二维网格中的边界上的点。首先，通过#include引入了stdio.h、stdlib.h和stdbool.h库，分别用于输入输出、动态内存分配和布尔类型。接下来，定义了常量MAX_N和MAX_M表示二维网格的最大行数和列数。然后，定义了全局变量n和m表示二维网格的实际行数和列数，以及一个二维数组dir表示上、左、下、右四个方向的移动。接着，定义了一个递归函数dfs，用于遍历二维网格。函数首先判断当前点是否已被访问过，如果是则直接返回。然后标记当前点为已访问。接着，对四个方向进行遍历：计算下一个点的坐标，判断是否越界或下一个点的高度小于当前点的高度，如果是则继续下一个方向的遍历。最后，递归调用dfs函数遍历下一个点。在main函数中，定义了一个二维数组grid表示二维网格，以及两个二维数组firstBorder和secondBorder表示第一条边界和第二条边界。然后通过scanf函数输入二维网格的行数和列数，并通过两层循环输入二维网格的元素。接着，通过两层循环分别遍历第一条边界和第二条边界的所有点，并调用dfs函数进行遍历。最后，再次遍历二维网格，如果某个点同时位于第一条边界和第二条边界上，则输出该点的坐标。最后，返回0表示程序正常结束。这段代码的时间复杂度为O(nm)，其中n和m分别为二维网格的行数和列数。
104.建造最大岛屿
思路
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAXN 100 // 假设最大网格大小为100x100
int n, m;
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
// 定义结构体来模拟C++中的vector和unordered_map
typedef struct {
int rows, cols;
int **data;
} Grid;
typedef struct {
int key;
int value;
struct Node* next;
} HashNode;
typedef struct {
HashNode** table;
int size;
} HashMap;
// 辅助函数：创建Grid
Grid createGrid(int rows, int cols) {
Grid grid;
grid.rows = rows;
grid.cols = cols;
grid.data = (int**)malloc(rows * sizeof(int*));
for (int i = 0; i < rows; i++) {
grid.data[i] = (int*)malloc(cols * sizeof(int));
}
return grid;
}
// 辅助函数：释放Grid
void freeGrid(Grid* grid) {
for (int i = 0; i < grid->rows; i++) {
free(grid->data[i]);
}
free(grid->data);
}
// 辅助函数：创建HashMap
HashMap createHashMap(int size) {
HashMap map;
map.size = size;
map.table = (HashNode**)calloc(size, sizeof(HashNode*));
return map;
}
// 辅助函数：释放HashMap
void freeHashMap(HashMap* map) {
for (int i = 0; i < map->size; i++) {
HashNode* current = map->table[i];
while (current != NULL) {
HashNode* temp = current;
current = current->next;
free(temp);
}
}
free(map->table);
}
// 辅助函数：计算哈希值
unsigned int hash(int key, int size) {
return key % size;
}
// 辅助函数：在HashMap中插入元素
void insertHashMap(HashMap* map, int key, int value) {
unsigned int index = hash(key, map->size);
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = map->table[index];
map->table[index] = newNode;
}
// 辅助函数：在HashMap中查找元素
int* findHashMap(HashMap* map, int key) {
unsigned int index = hash(key, map->size);
HashNode* current = map->table[index];
while (current != NULL) {
if (current->key == key) {
return &(current->value);
}
current = current->next;
}
return NULL;
}
// 深度优先搜索函数
void dfs(Grid* grid, bool** visited, int x, int y, int mark) {
if (visited[x][y] || grid->data[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
visited[x][y] = true; // 标记访问过
grid->data[x][y] = mark; // 给陆地标记新标签
count++;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue; // 越界了，直接跳过
dfs(grid, visited, nextx, nexty, mark);
}
}
int main() {
scanf("%d %d", &n, &m);
Grid grid = createGrid(n, m);
bool** visited = (bool**)malloc(n * sizeof(bool*));
for (int i = 0; i < n; i++) {
visited[i] = (bool*)calloc(m, sizeof(bool));
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &grid.data[i][j]);
}
}
HashMap gridNum = createHashMap(MAXN);
int mark = 2; // 记录每个岛屿的编号
bool isAllGrid = true; // 标记是否整个地图都是陆地
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid.data[i][j] == 0) isAllGrid = false;
if (!visited[i][j] && grid.data[i][j] == 1) {
count = 0;
dfs(&grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
int* area = findHashMap(&gridNum, mark);
if (area == NULL) {
insertHashMap(&gridNum, mark, count); // 记录每一个岛屿的面积
} else {
// In case of hash collision (though unlikely with small keys), update the value
*area = count;
}
mark++; // 记录下一个岛屿编号
}
}
}
if (isAllGrid) {
printf("%d\n", n * m); // 如果都是陆地，返回全面积
freeGrid(&grid);
for (int i = 0; i < n; i++) {
free(visited[i]);
}
free(visited);
freeHashMap(&gridNum);
return 0; // 结束程序
}
// 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和
int result = 0; // 记录最后结果
bool* visitedGrid = (bool*)calloc(MAXN, sizeof(bool)); // 标记访问过的岛屿
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
count = 1; // 记录连接之后的岛屿数量
for (int k = 0; k < MAXN; k++) {
visitedGrid[k] = false; // 每次使用时，清空（虽然这里有点浪费，但为了简单处理）
}
if (grid.data[i][j] == 0) {
for (int k = 0; k < 4; k++) {
int neari = i + dir[k][1]; // 注意：这里的dir数组索引和C++代码中的顺序是反的，因为C语言中数组索引从0开始，而原C++代码中的方向数组是顺时针排列的，为了保持一致性，这里做了调整
int nearj = j + dir[k][0];
if (neari < 0 || neari >= n || nearj < 0 || nearj >= m) continue;
int nearIsland = grid.data[neari][nearj];
if (visitedGrid[nearIsland]) continue; // 添加过的岛屿不要重复添加
// 把相邻四面的岛屿数量加起来
int* area = findHashMap(&gridNum, nearIsland);
if (area != NULL) {
count += *area;
}
visitedGrid[nearIsland] = true; // 标记该岛屿已经添加过
}
}
if (count > result) {
result = count;
}
}
}
printf("%d\n", result);
// 释放内存
freeGrid(&grid);
for (int i = 0; i < n; i++) {
free(visited[i]);
}
free(visited);
free(visitedGrid);
freeHashMap(&gridNum);
return 0;
}原文地址：https://blog.csdn.net/a6666999d/article/details/143913232
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！