代码随想录算法训练营第五十二天|Day52 图论-水流问题

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分别为二维网格的行数和列数。