代码随想录 103. 水流问题

103. 水流问题

#include<bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>>& mp, vector<vector<int>>& visit, int y, int x){
    if (visit[y][x] == 1) return;
    visit[y][x] = 1;
    if (y > 0){
        if (mp[y][x] <= mp[y - 1][x]){
            dfs(mp, visit, y - 1, x);
        }
    }
    if (x > 0){
        if (mp[y][x] <= mp[y][x - 1]){
            dfs(mp, visit, y, x - 1);
        }
    }
    if (y < mp.size() - 1){
        if (mp[y][x] <= mp[y + 1][x]){
            dfs(mp, visit, y + 1, x);
        }
    }
    if (x < mp[0].size() - 1){
        if (mp[y][x] <= mp[y][x + 1]){
            dfs(mp, visit, y, x + 1);
        }
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> mp(n, vector<int>(m, 0));
    vector<vector<int>> visit1(n, vector<int>(m, 0));
    vector<vector<int>> visit2(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> mp[i][j];
        }
    }
    for (int i = 0; i < n; i++){
        dfs(mp, visit1, i, 0);
        dfs(mp, visit2, i, m - 1);
    }
    for (int i = 0; i < m; i++){
        dfs(mp, visit1, 0, i);
        dfs(mp, visit2, n - 1, i);
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (visit1[i][j] == 1 && visit2[i][j] == 1){
                cout << i << " " << j << "\n";
            }
        }
    }
    
    return 0;
}

笔者想出的是随想录中比较暴力的解法，笔者想过对暴力的这种做优化，比如在dfs的遍历过程中对节点做标记，标记节点能到哪一类边界，之后的遍历中将周围节点的判决作为依据，减少计算量，但想了想还是有不妥。因为在遍历中很重要的一步是对遍历的流向做限制，比如先遇到的节点是[0][0]，那么之后可以从[0][0]到[0][1]，但在进入[0][1]后不能再对[0][0]做访问，这是为了避免遍历陷入无限的循环，但在这题中，相同高度的两类节点间，流向是双向的，也就意味着笔者的优化想法会舍弃掉一种流向，导致潜在的错误，而对这个情况，笔者所能想到的解决方法是只对能流到两类边界的节点做标记，但这样同时也会导致一些点被遍历多次的情况出现。

所以笔者还是看了看更巧妙的逆流而上的解法来写。逆流而上的优势在于，遍历过程中只需要考虑一类边界逆流而上所能到达的范围，不需要考虑双向流向，所以在遍历过程中可以对节点做标记，对已经做标记的节点不需要做操作，在对两类边界都遍历一次后，取两个范围的交集即可，最极端的情况也只需对所有点做2次访问就能确定。

代码随想录 103. 水流问题