解題區/解題區 - UVa

UVa 12265 - Selling Land

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

求以每個點當作矩形右下角，找到所有最大周長矩形的所有情況。

Sample Input

1
2
3
4
5
6
7
8
1
6 5
..#.#
.#...
#..##
...#.
#....
#..#.

Sample Output

1
2
3
4
5
6 x 4
5 x 6
5 x 8
3 x 10
1 x 12

Solution

作法類似於最大矩形，主要改變的是單調堆的操作，當增加的周長幅度不夠時，則將不會丟入單調堆中。換句話說，增加幅度不足時，如果將這個高度丟入 (水平寬度會增加，垂直高度會減少)，對於下一個點而言，沿用前一個會使得周長更長。

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
74
75
76
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#define maxL ((1024*1024)>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
using namespace std;
int mark[maxL];
void solve(int n, int h[], int record[]) {
    int i, height;
    stack< pair<int, int> > stk;// <height, position>
    pair<int, int> e;
    h[n] = 0;// visual height.
    for(i = 0; i <= n; i++) {
        height = h[i];
        e = make_pair(height, i);
        while(!stk.empty() && height <= stk.top().first)
            e = stk.top(), stk.pop();
        if (height == 0)
            continue;
        if(stk.empty() || height - stk.top().first > e.second - stk.top().second) {
            record[height + (i - e.second + 1)]++;
            stk.push(make_pair(height, e.second));
        } else {
            record[stk.top().first + (i - stk.top().second + 1)]++;
        }
    }
}
int n, m, h[1024];
int main() {
    int testcase;
    char line[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
    	memset(mark, 0, sizeof(mark));
    	memset(h, 0, sizeof(h));
        for(int i = 0; i < n; i++) {
        	scanf("%s", line);
            for (int j = 0; j < m; j++) {
                if (line[j] == '.') {
                    SET(i * 1024 + j);
                }
            }
        }
        int record[2048] = {};
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	if(GET(j * 1024 + i))
            		h[j]++;
            	else
            		h[j] = 0;
            }
            solve(n, h, record);
        }
        for (int i = 1; i <= n+m; i++) {
            if (record[i]) {
                printf("%d x %d\n", record[i], i<<1);
            }
        }
    }
    return 0;
}
/*
 1
 6 5
 ..#.#
 .#...
 #..##
 ...#.
 #....
 #..#.
 */