UVa 12265 - Selling Land

链接

传送门

题意

给出$n \times m$的矩阵,’#’代表沼泽,’.’代表空地,对于每个点向右上方能扩展到周长最大的矩形,记录不同周长的矩形的个数。

思路

对于每一行维护举行高度和左边界的单调栈。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1005;
const int maxm = 2005;
int h[maxn], ans[maxm];
char s[maxn];
int r[maxn], c[maxn];
int main(){
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
memset(h, 0, sizeof h);
memset(ans, 0, sizeof ans);
for (int i = 0; i < n; ++i) {
scanf("%s", s);
int p = -1;
for (int j = 0; j < m; ++j) {
if (s[j] == '.') {
++h[j];
int cc = j;
while (p >= 0 && r[p] >= h[j]) {
cc = c[p--];
}
if (p == -1 || r[p] - c[p] < h[j] - cc) {
++p;
r[p] = h[j];
c[p] = cc;
}
++ans[r[p] + j + 1 - c[p]];
} else {
p = -1;
h[j] = 0;
}
}
}
for (int i = 0; i < maxm; ++i) {
if (ans[i] > 0) {
printf("%d x %d\n", ans[i], i << 1);
}
}
}
return 0;
}

支付宝扫码领红包