#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 505
struct Maps {
int num , h;
Maps (int num = 0 , int h = 0):
num(num) , h(h) {}
};
const int dx[4] = {1 , 0 , -1 , 0};
const int dy[4] = {0 , 1 , 0 , -1};
int n , m , inp[MAXN*MAXN] , out[MAXN*MAXN] , in , ou;
int dfn[MAXN*MAXN] , low[MAXN*MAXN] , scc[MAXN*MAXN] , scid , visid;
bool is[MAXN*MAXN] , vis[MAXN*MAXN];
stack <int> s;
Maps map[MAXN][MAXN];
vector <int> v[MAXN*MAXN];
void tanjan (int u)
{
dfn[u] = low[u] = ++ visid;
is[u] = true , vis[u] = true , s.push(u);
for(auto i : v[u])
{
if(vis[i] == false){
tanjan (i);
low[u] = min (low[u] , low[i]);
}
else if (is[u])
low[u] = min (low[u] , dfn[i]);
}
// printf ("test in --> u = %d low[u] = %d dfn[u] = %d\n",u,low[u],dfn[u]);
if(low[u] == dfn[u])
{
int p;
++ scid;
do {
p = s.top(); s.pop();
is[p] = false , scc[p] = scid;
} while (p != u);
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= m ; j ++)
{
scanf("%d",&map[i][j].h);
map[i][j].num = (i-1)*m+j;
}
}
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= m ; j ++)
{
for(int k = 0 ; k < 4 ; k ++)
{
int tx = i + dx[k] , ty = j + dy[k];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && map[i][j].h >= map[tx][ty].h)
{
v[map[i][j].num].push_back(map[tx][ty].num);
}
}
}
}
for(int i = 1 ; i <= n*m ; i ++)
if(vis[i] == false) tanjan (i);
// cout << "scc[14] = " << scc[14] << '\n';
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= m ; j ++)
{
for(auto k : v[map[i][j].num])
{
// if(map[i][j].h == 3)
// {
// cout << "k == " << k << " scc[k] == " << scc[k] << '\n';
// cout << int(scc[map[i][j].num] != scc[k]) << '\n';
// }
if(scc[map[i][j].num] != scc[k])
{
++ inp[scc[k]];
++ out[scc[map[i][j].num]];
// printf("ins --> k = {%d %d scc = %d} map[%d][%d] = {%d %d scc = %d} inp[%d] = %d out[%d] = %d\n",k,k.h,scc[k.num],i,j,map[i][j].num,map[i][j].h,scc[map[i][j].num],scc[k.num],inp[scc[k.num]],scc[map[i][j].num],out[scc[map[i][j].num]]);
}
}
}
}
for(int i = 1 ; i <= scid ; i ++)
{
if(inp[i] == 0) ++ in;
if(out[i] == 0) ++ ou;
}
// printf ("test --> in = %d ou = %d\n",in,ou);
cout << max (in , ou) << '\n';
return 0;
}
非常求助,样例没过但55分,怀疑tanjan算法出错或者是枚举时出错,但自己测试查不出错误,谢谢大佬