原题链接

题解

非常抽象的缩点
大概思路：搜索缩点成有向图，求该点的入度和出度，最后答案一定是 \(max(in,out)\)
总之很抽象

code

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

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

ll n, m;
ll a[505][505] = {0};
ll xx[4] = {1, 0, -1, 0}, yy[4] = {0, 1, 0, -1};
ll vis[505][505] = {0};
ll in[250005] = {0};//任何有向图一定可以表示为一颗倒着的树，如图
ll out[250005] = {0};
ll cnt = 0;

void ss(ll val, ll x, ll y)
{
    vis[x][y] = 1;
    for(ll i = 0; i < 4; i++)
    {
        ll x1 = x + xx[i], y1 = y + yy[i];
        if(x1 > 0 && x1 <= n && y1 > 0 && y1 <= m)
        {
            if(a[x1][y1] == val)
            {
                if(!vis[x1][y1]) ss(val, x1, y1);
            }
            else if(a[x1][y1] < val) out[cnt]++;
            else if(a[x1][y1] > val) in[cnt]++;
        }
    }
}

int main()
{
    read(m); read(n);

    for(ll i = 1; i <= n; i++)
        for(ll j = 1; j <= m; j++)
            read(a[i][j]);

    for(ll i = 1; i <= n; i++)
        for(ll j = 1; j <= m; j++)
            if(!vis[i][j])
            {
                cnt++;
                ss(a[i][j], i, j);
            }

    ll ins = 0, outs = 0;
    for(ll i = 1; i <= cnt; i++)
    {
        ins += (!in[i]);
        outs += (!out[i]);
    }

    if(cnt == 1) puts("0");//细节
    else write(max(ins, outs)), putchar('\n');
    return 0;
}