1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <bits/stdc++.h>
#define max(x,y) (x ^ ((x ^ y) & -(x < y)))
#define MAX 100000
#define INF 0x3ffffff
using namespace std;
const int dx[] = { -1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int dfn[MAX], low[MAX];
int st[MAX];
bool vis[MAX], f[MAX];
int g[305][305], rg[305][305];
bool r[MAX], c[MAX];
int deg[MAX];
int size, tot, num, top, n, m;
vector <int> vc[MAX];
inline void tarjan(int x) {
tot++;
while (st[top] ^ x)
f[st[top]] = false, deg[st[top]] = tot, top--;
f[st[top]] = false;
deg[st[top]] = tot;
top--;
}
void dfs(int x) {
size++;
dfn[x] = size;
low[x] = size;
top++;
st[top] = x;
f[x] = true;
for (int i = 0; i < vc[x].size(); i++)
if (!dfn[vc[x][i]])
dfs(vc[x][i]), low[x] = min(low[x], low[vc[x][i]]);
else if (f[vc[x][i]])
low[x] = min(low[x], low[vc[x][i]]);
if (dfn[x] == low[x]) tarjan(x);
}
inline void degree() {
int tot1 = 0, tot2 = 0;
for (int i = 1; i <= num; i++)
for (int j = 0; j < vc[i].size(); j++)
if (deg[i]^deg[vc[i][j]])
c[deg[i]] = true, r[deg[vc[i][j]]] = true;
for (int i = 1; i <= tot; i++) {
if (!c[i]) tot1++;
if (!r[i]) tot2++;
}
cout << max(tot1, tot2);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
memset(g, 127, sizeof(g));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> g[i][j], rg[i][j] = ++num;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < 4; k++)
if (g[i][j] >= g[i + dx[k]][j + dy[k]])
vc[rg[i][j]].push_back(rg[i + dx[k]][j + dy[k]]);
if (n == 1 && m == 1)
cout << "0\n", exit(0);
for (int i = 1; i <= num; i++)
if (!dfn[i])
dfs(i);
degree();
return 0;
}
|
