POJ 1964 - City Game

http://poj.org/problem?id=1964

概要

\(M \times N\) のグリッドについて、各マスが空いているかどうかが与えられる。 このグリッドの中の空いている長方形の領域で最大のものの面積の3倍を答える。

制約

解法

前処理により、あるマスから上にいくつ連続で空いたマスがあるかを調べることができる。 すると、各行でいわゆる「ヒストグラムから最大の長方形の面積を答える」問題を解けばいいことになり、 これはスタックを用いて \(O(N)\) で解けるため、全体で \(O(MN)\) で解ける。

 1 #include <cstdio>
 2 #include <stack>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int max_rect(const int *hist, int N)
 7 {
 8   stack<pair<int,int> > stk;
 9   int prev_h = -1;
10   int ans = 0;
11   for (int i = 0; i < N; i++) {
12     const int w = 1, h = hist[i];
13     if (h >= prev_h) {
14       stk.push(make_pair(w, h));
15     } else {
16       int width = 0;
17       while (!stk.empty() && stk.top().second > h) {
18         width += stk.top().first;
19         ans = max(ans, width * stk.top().second);
20         stk.pop();
21       }
22       width += w;
23       stk.push(make_pair(width, h));
24     }
25     prev_h = h;
26   }
27   for (int width = 0; !stk.empty(); stk.pop()) {
28     width += stk.top().first;
29     ans = max(ans, width * stk.top().second);
30   }
31   return ans;
32 }
33 
34 int main()
35 {
36   int T;
37   scanf("%d", &T);
38   while (T-- > 0) {
39     int H, W;
40     scanf("%d %d", &H, &W);
41     static int hist[1000+1][1000];
42     for (int i = 1; i <= H; i++) {
43       for (int j = 0; j < W; j++) {
44         char buf[4];
45         scanf("%s", buf);
46         if (*buf == 'F') {
47           hist[i][j] = hist[i-1][j] + 1;
48         } else {
49           hist[i][j] = 0;
50         }
51       }
52     }
53     int ans = 0;
54     for (int i = 1; i <= H; i++) {
55       ans = max(ans, max_rect(hist[i], W));
56     }
57     printf("%d\n", ans*3);
58   }
59   return 0;
60 }
poj/1964.cc