《算法提高课》题解与笔记上线啦！(链接就是这个){: style=”color: #FF0000”}

创建时间2024-4-5

$$ #1 1106.山峰和山谷 $$

Flood Fill

原题Link

Code:

# include <bits/stdc++.h>
# define sc scanf
# define fr front
# define pr printf
# define fir first
# define sec second
using namespace std;

const int N = 1e3 + 10;

typedef pair<int, int> PII;

int n, p, v;
int h[N][N];
bool vis[N][N];

void BFS(int sx, int sy, bool& higher, bool& lower){ // 引用可在 BFS 中改变 higher 和 lower 的值 
    queue<PII> q;
    q.push({sx, sy});
    vis[sx][sy] = true;

    while(!q.empty()){
        int x = q.fr().fir;
        int y = q.fr().sec;
        q.pop();

        for(int i = x - 1; i <= x + 1; i ++){
            for(int j = y - 1; j <= y + 1; j ++){
                if(i < 1 || i > n || j < 1 || j > n) continue;

                if(h[x][y] != h[i][j]){ // 山脉的边界
                    if(h[i][j] > h[x][y]) higher = true;
                    else lower = true;
                }

                else if(!vis[i][j]){ // 高度相同才是一个平面 
                    q.push({i, j});
                    vis[i][j] = true;
                }
            }
        }
    }
}

int main(){
    sc("%d", &n);

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            sc("%d", &h[i][j]);

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(!vis[i][j]){
                bool higher = false, lower = false;
                BFS(i, j, higher, lower);
                if(!higher) p ++; // 山峰 
                if(!lower) v ++; // 山谷 
            }
        }
    }

    pr("%d %d", p, v);

    return 0;
}