算法提高课汇总

算法思路

统计连通块(边界)与其相邻节点的关系:

• 8联通, 若边界节点高度全部大于/小于相邻节点, 则称为山峰/山谷.

• 在入队时判断相邻点是否属于当前联通块, 若不属于则判断高度关系.

• 实现时, 只需要判断是否存在有低于/高于当前节点的相邻点即可.

代码实现

#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int N = 1010;

int n;
int h[N][N];
pii q[N * N];
bool st[N][N];

void bfs(int sx, int sy, bool &has_up, bool &has_down)
{
    int hh = 0, tt = 0;
    q[tt ++] = {sx, sy};
    st[sx][sy] = true;

    while( hh < tt )
    {
        pii cur = q[hh ++];
        int x = cur.x, y = cur.y;
        for( int nx = x - 1; nx <= x + 1; nx ++ )
            for(int ny = y - 1; ny <= y + 1; ny ++ )
            {
                if( nx < 0 || nx >= n || ny < 0 || ny >= n ) continue;
                if( h[nx][ny] != h[x][y] )
                {//相邻节点
                    if( h[nx][ny] > h[x][y] )   has_up = true;
                    else    has_down = true;
                }
                else if( !st[nx][ny] )
                {
                    st[nx][ny] = true;
                    q[tt ++] = {nx, ny};
                }
            }
    }
}

int main()
{
    cin >> n;
    for( int i = 0; i < n; i ++ )
        for( int j = 0; j < n; j ++ )
            cin >> h[i][j];

    int up = 0, down = 0; //山峰; 山谷数目
    for( int i = 0; i < n; i ++ )
        for( int j = 0; j < n; j ++ )
            if( !st[i][j] )
            {
                bool has_up = false, has_down = false;
                bfs(i, j, has_up, has_down);
                if( !has_up ) up ++;
                if( !has_down )   down ++;
            }
    cout << up << ' ' << down << endl;

    return 0;
}