|
|
#include <stdio.h>
|
|
|
#include <iostream>
|
|
|
#include <map>
|
|
|
#include <algorithm>
|
|
|
#include <queue>
|
|
|
#include <string>
|
|
|
#include <cstring>
|
|
|
#include <vector>
|
|
|
|
|
|
// C++可以AC，G++直接挂掉
|
|
|
using namespace std;
|
|
|
const int MAXN = 550; // 原来矩阵的长宽最大值
|
|
|
const int N = MAXN * MAXN, M = N << 2; // 新建图的点个数，及边个数，此题的边比较多 普通的N<<1不够
|
|
|
int g[MAXN][MAXN]; // 原始地势高低的矩阵
|
|
|
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// Tarjan算法求强连通分量
|
|
|
int dfn[N], low[N], ts;
|
|
|
int stk[N], top;
|
|
|
int in_stk[N];
|
|
|
int id[N], scc_cnt;
|
|
|
int din[N], dout[N];
|
|
|
void tarjan(int u) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
in_stk[u] = 1;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
} else if (in_stk[v])
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++scc_cnt;
|
|
|
int x;
|
|
|
do {
|
|
|
x = stk[top--];
|
|
|
in_stk[x] = 0;
|
|
|
id[x] = scc_cnt;
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int n, m; // 行数与列数
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("NC106972.in", "r", stdin);
|
|
|
#endif
|
|
|
memset(h, -1, sizeof h); // 初始化链式前向星
|
|
|
scanf("%d %d", &m, &n); // 败家的东西，先输入m后输入n
|
|
|
|
|
|
// 输入原始数据矩阵
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = 1; j <= m; j++)
|
|
|
scanf("%d", &g[i][j]);
|
|
|
|
|
|
// 根据题意，向四边探索建图,建图用的点号计算办法(x-1)*m+y
|
|
|
for (int x = 1; x <= n; x++)
|
|
|
for (int y = 1; y <= m; y++) {
|
|
|
int id = (x - 1) * m + y;
|
|
|
if (x > 1 && g[x][y] >= g[x - 1][y]) add(id, id - m); // 上一行
|
|
|
if (x < n && g[x][y] >= g[x + 1][y]) add(id, id + m); // 下一行
|
|
|
if (y > 1 && g[x][y] >= g[x][y - 1]) add(id, id - 1); // 左一列
|
|
|
if (y < m && g[x][y] >= g[x][y + 1]) add(id, id + 1); // 右一列
|
|
|
}
|
|
|
|
|
|
// 注意点的个数为n*m
|
|
|
for (int i = 1; i <= n * m; i++)
|
|
|
if (!dfn[i]) tarjan(i);
|
|
|
|
|
|
// 遍历每条出边，看看此边的两个端点是不是在同一个连通分量中，如果不是，标识两个连通分量间的出度入度变化
|
|
|
for (int u = 1; u <= n * m; u++) {
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
int a = id[u], b = id[v];
|
|
|
if (a != b)
|
|
|
dout[a]++, din[b]++;
|
|
|
}
|
|
|
}
|
|
|
// 统计所有连通分量入度、出度为零的个数
|
|
|
// 将出度入度为零的强连通分量间建边，可以最少代价完成强连通补边
|
|
|
int a = 0, b = 0;
|
|
|
for (int i = 1; i <= scc_cnt; i++) {
|
|
|
if (!din[i]) a++;
|
|
|
if (!dout[i]) b++;
|
|
|
}
|
|
|
if (scc_cnt == 1) // 特判一个强连通分量的特殊情况
|
|
|
printf("0\n");
|
|
|
else
|
|
|
printf("%d\n", max(a, b)); // 输出两者最大值
|
|
|
return 0;
|
|
|
}
|
