2011-08-04 17:49:57Morris
b018. F. 營地
b018. F. 營地
/**********************************************************************************/
/* Problem: b018 "F. 營地" from 2006 NPSC 高中組初賽 */
/* Language: C */
/* Result: AC (156ms, 288KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-04 15:42:18 */
/**********************************************************************************/
#include<stdio.h>
char s[20000];
main() {
int n, m, a, b, c;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0) break;
int DP1[5001] = {}, DP2[5001] = {};
int *A = DP1, *B = DP2, *C, Ans = 0;
getchar();
int L = 2*m-1;
for(a = 0; a < n; a++) {
gets(s);
for(b = 0, c = 1; b < L; b += 2, c++) {
if(s[b] != '2') {
B[c] = A[c];
B[c] = B[c] < A[c-1] ? B[c] : A[c-1];
B[c] = B[c] < B[c-1] ? B[c] : B[c-1];
B[c]++;
Ans = Ans > B[c] ? Ans : B[c];
}
else {B[c] = 0;}
}
C = A, A = B, B= C;
}
printf("%d\n", Ans*Ans);
}
return 0;
}
內容 ：
露營時都搭過帳棚吧？但帳棚也不是說搭就搭，必須要有一塊平坦的空地才行，否則就必須要先整理場地，清除石塊、雜物才能搭好。但也不是說清理就清理，有時候如果出現很大塊的石頭或是大型的坑洞，帳篷就不得不避開這樣的地方。
清理好場地以後，要搭怎麼樣的帳棚呢？雖然大部分是依場地而定，但對於初學者可能還是以特定的形狀為宜。
現在給你一塊空地的資料，請你計算出在這營地上能夠搭建帳篷的最大面積。為了簡化問題，假設營地為一 L * W 的矩形，並分為 L * W 個方格，方格為場地的最小單位，一個方格內的場地特性視為一體。並限制所搭帳篷的形狀必須是正方形，且帳篷的四邊和營地的四邊分別對應平行。
輸入說明
：
輸入含有多筆測試資料，每筆資料第一行有兩個數字
L, W（1 ≦ L, W ≦ 5000），代表場地的長和寬。接下來 L 行每行有 W
個介於0~2之間的整數，代表每一塊方格的資料，0代表此格可以直接使用，1表示必須經過整理，2表示有無法清理的障礙物。第一行為兩個零時表示檔案結
束，不須處理這組輸入。
輸出說明
：
每筆資料輸出一行，含有一個正整數，代表最大帳篷的面積。
範例輸入 ：
4 5 1 0 0 2 0 0 1 1 0 0 0 2 1 1 1 1 0 0 1 2 0 0
範例輸出 ：
4
提示
：
* 注意：這個題目若直接宣告 5000 * 5000 的陣列會出 Runtime Error。請用較少的陣列解決這個問題。
出處
：
2006 NPSC 高中組初賽
作法 : DP
紀錄某一格能做的最大正方形, 抓左上, 上方, 左方, 的最小值+1 成為新的正方形
作法 : DP
紀錄某一格能做的最大正方形, 抓左上, 上方, 左方, 的最小值+1 成為新的正方形
/**********************************************************************************/
/* Problem: b018 "F. 營地" from 2006 NPSC 高中組初賽 */
/* Language: C */
/* Result: AC (156ms, 288KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-04 15:42:18 */
/**********************************************************************************/
#include<stdio.h>
char s[20000];
main() {
int n, m, a, b, c;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0) break;
int DP1[5001] = {}, DP2[5001] = {};
int *A = DP1, *B = DP2, *C, Ans = 0;
getchar();
int L = 2*m-1;
for(a = 0; a < n; a++) {
gets(s);
for(b = 0, c = 1; b < L; b += 2, c++) {
if(s[b] != '2') {
B[c] = A[c];
B[c] = B[c] < A[c-1] ? B[c] : A[c-1];
B[c] = B[c] < B[c-1] ? B[c] : B[c-1];
B[c]++;
Ans = Ans > B[c] ? Ans : B[c];
}
else {B[c] = 0;}
}
C = A, A = B, B= C;
}
printf("%d\n", Ans*Ans);
}
return 0;
}
IO加速又一招