G Selling Land
As you may know, the country of Absurdistan is full of abnormalities. For example, the whole country can be divided into unit squares that are either grass or swamp. Also, the country is famous for its incapable
bureaucrats. If you want to buy a piece of land (called a parcel), you can only buy a rectangular area, because they cannot handle other shapes. The price of the parcel is determined by them and is proportional to the perimeter of the parcel, since the bureaucrats
are unable to multiply integers and thus cannot calculate the area of the parcel.
Per owns a parcel in Absurdistan surrounded by swamp and he wants to sell it, possibly in parts, to some buyers. When he sells a rectangular part of his land, he is obliged to announce this to the local bureaucrats.
They will first tell him the price he is supposed to sell it for. Then they will write down the name of the new owner and the coordinates of the south-east corner of the parcel being sold. If somebody else already owns a parcel with a south-east corner at
the same spot, the bureaucrats will deny the change of ownership.
Per realizes that he can easily trick the system. He can sell overlapping areas, because bureaucrats only check whether the south-east corners are identical. However, nobody wants to buy a parcel containing swamp.
Figure 1: In this example, dark squares represent swamp. Per may, for example, sell three overlapping grey areas, with dimensions 2×1, 2×4 and 4×1 respectively. The total perimeter is 6 + 12 + 10=28. Note that
he can get more money by selling even more land. This figure cZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcnJlc3BvbmRzIHRvIHRoZSBjYXNlIGluIHRoZSBzYW1wbGUgaW5wdXQuPC9jZW50ZXI+CgpOb3cgUGVyIHdvdWxkIGxpa2UgdG8ga25vdyBob3cgbWFueSBwYXJjZWxzIG9mIGVhY2ggcGVyaW1ldGVyIGhlIG5lZWRzIHRvIHNlbGwgaW4gb3JkZXIgdG8gbWF4aW1pemUgaGlzIHByb2ZpdC4gQ2FuIHlvdSBoZWxwIGhpbT8gWW91IG1heSBhc3N1bWUgdGhhdCBoZSBjYW4gYWx3YXlzIGZpbmQgYSBidXllciBmb3IgZWFjaCBwaWVjZSBvZiBsYW5kLCBhcyBsb25nCiBhcyBpdCBkb2Vzbg=="t contain any swamps. Also, Per is sure that no square within his parcel is owned by somebody else.
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
One line with two integers n and m (1 ≤ n, m ≤ 1 000): the dimensions of Per's parcel.
n lines, each with m characters. Each character is either `#' or `.'. The j-th character on the i-th line is a `#' if position (i, j) is a swamp, and `.' if it is grass. The north-west corner of Per's parcel has coordinates
(1, 1), and the south-east corner has coordinates (n,m).
Output
Per test case:
Zero or more lines containing a complete list of how many parcels of each perimeter Per needs to sell in order to maximize his profit. More specifically, if Per should sell pi parcels of perimeter i in the optimal solution, output a single line
"pi x i". The lines should be sorted in increasing order of i. No two lines should have the same value of i, and you should not output lines with pi=0.
Sample in- and output
Input
Output
1
6 5
..#.#
.#...
#..##
...#.
#....
#..#.
6 x 4
5 x 6
5 x 8
3 x 10
1 x 12
題意：一塊n*m的土地，以每個右下角點為起點，向左向上找一個最大周長的矩形，最後統計個數輸出每種周長矩形的個數。
思路：先把每一行對應每個位置豎直方向的最大值預處理出來，然後每一行利用單調隊列去維護，因為如果前一個長於後一個，那麼後一個在選矩形的時候高度肯定不會超過他本身，就不會達到前一個高度，所以前一個高度等同於沒用，然後維護過程中注意最大值的更新方式，看豎直方向和水平方向往那邊延伸的收益大，就可以判斷出高度是要用他本身還是前一個的高度。
代碼：
#include
#include
#include
using namespace std;
const int N = 1005;
typedef pair pi;
int t, n, m, up[N][N], ans[2 * N];
char str[N];
void solve() {
memset(ans, 0, sizeof(ans));
for (int i = 1; i <= n; i++) {
dequeQ;
for (int j = 1; j <= m; j++) {
int r = j;
while (!Q.empty() && Q.back().first >= up[i][j]) {
r = Q.back().second;
Q.pop_back();
}
if (up[i][j] == 0) continue;
if (Q.empty() || up[i][j] - Q.back().first > r - Q.back().second) {
ans[up[i][j] + j - r + 1]++;
Q.push_back(make_pair(up[i][j], r));
}
else ans[j - Q.back().second + 1 + Q.back().first]++;
}
}
for (int k = 2; k <= n + m; k++)
if (ans[k]) printf("%d x %d\n", ans[k], k * 2);
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", str + 1);
for (int j = 1; j <= m; j++) {
if (str[j] == '#') up[i][j] = 0;
else up[i][j] = up[i - 1][j] + 1;
}
}
solve();
}
return 0;
}
