回分類題庫
h020: F.營地
關鍵字: NPSC 2006 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 44 Times / 35 Users | Submit : 155 Times / 42 Users | Accepted rate : 83%
題目加入時間 : 2011-11-10 10:32

Content: 简体中文

露營時都搭過帳棚吧?但帳棚也不是說搭就搭,必須要有一塊平坦的空地才行,否則就必須要先整理場地,清除石塊、雜物才能搭好。但也不是說清理就清理,有時候如果出現很大塊的石頭或是大型的坑洞,帳篷就不得不避開這樣的地方。

清理好場地以後,要搭怎麼樣的帳棚呢?雖然大部分是依場地而定,但對於初學者可能還是以特定的形狀為宜。

現在給你一塊空地的資料,請你計算出在這營地上能夠搭建帳篷的最大面積。為了簡化問題,假設營地為一 LxW 的矩形,並分為 LxW 個方格,方格為場地的最小單位,一個方格內的場地特性視為一體。並限制所搭帳篷的形狀必須是正方形,且帳篷的四邊和營地的四邊分別對應平行。

Input:

輸入含有多筆測試資料,每筆資料第一行有兩個數字L, W(1 <= L, W <= 5000),代表場地的長和寬。接下來 L 行每行有 W 個介於0~2之間的整數,代表每一塊方格的資料,0代表此格可以直接使用,1表示必須經過整理,2表示有無法清理的障礙物。第一行為兩個零時表示檔案結束,不須處理這組輸入。

Output:

每筆資料輸出一行,含有一個正整數,代表最大帳篷的面積。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4 5
1 0 0 2 0
0 1 1 0 0
0 2 1 1 1
1 0 0 1 2
0 0

Sample Output :

4

Hint :

因測資檔過大,請注意輸入優化以及記憶體優化。

Author :

NPSC 2006 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum