#include <bits/stdc++.h>
struct path {
int x, y;
};
using namespace std;
int v[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
path s[260000]; int f[505][505]; int t[600]; path b[600];
int a[505][505];
bool cmp(path a, path b) {
if (a.y == b.y)
return (a.x < b.x);
return (a.y > b.y);
}
int main() {
path mid;
int i, j, n, m, k, g, cc = 0, l, r;
freopen("flow.in", "r", stdin);
freopen("flow.out", "w", stdout);
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) scanf("%d", &a[i][j]);
memset(t, 0, sizeof(0));
a[1][0] = -10086;
a[1][m + 1] = -10086;
for (i = 1; i <= m; i++) {
if (a[1][i] < a[1][i - 1] || a[1][i] < a[1][i + 1]) continue;
else {
cc++;
memset(f, 0, sizeof(f));
for (j = 0; j <= n + 1; j++) {
f[j][0] = 1;
f[j][m + 1] = 1;
}
for (j = 0; j <= m + 1; j++) {
f[0][j] = 1;
f[n + 1][j] = 1;
}
b[cc].x = m + 1;
b[cc].y = 0;
k = 0;
g = 0;
s[0].x = 1;
s[0].y = i;
while (k <= g) {
f[s[k].x][s[k].y] = 1; if (s[k].x == n) {
b[cc].x = min(b[cc].x, s[k].y); b[cc].y = max(b[cc].y, s[k].y); t[s[k].y] = 1; }
for (j = 0; j < 4; j++) {
mid.x = s[k].x + v[j][0];
mid.y = s[k].y + v[j][1];
if (!f[mid.x][mid.y] && a[mid.x][mid.y] < a[s[k].x][s[k].y]) {
g++;
s[g].x = mid.x;
s[g].y = mid.y;
}
}
k++;
}
if (b[cc].x == m + 1)
cc--;
}
}
int sum = 0;
for (i = 1; i <= m; i++) sum += t[i];
if (sum < m)
cout << "0"
<< "\n"
<< m - sum;
else
{
sort(b + 1, b + 1 + cc, cmp);
int vv = 0, tt = m, st = 1;
while (tt > 0) {
l = b[st].x;
r = st;
for (i = st + 1; i <= cc; i++)
if (b[i].y >= tt) {
if (b[i].x < l) {
l = b[i].x;
r = i;
}
}
else break;
vv++;
tt = l - 1;
st = i;
}
cout << "1"
<< "\n"
<< vv << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
共 2 条回复
建议附加scanf printf @novice
@novice 建议用函数