切換
舊版
前往
大廳
主題

ZeroJudge - e560: 10074 - Take the Land　解題心得

Not In My Back Yard | 2019-12-11 21:06:16 | 巴幣 106 | 人氣 516
題目連結：
題目大意：
輸入有若干筆測試資料。每筆第一列給定兩正整數 M 、 N （1 ≦ M 、 N ≦ 100），代表接下來有 M 列的輸入，每列有 N 個整數（只會是 0 或是 1 ，分別代表土地以及樹林）。其 M × N 個整數代表土地與樹林的分布圖。

試問只包含土地（即整數 0 ）的矩形，面積最大為何？

範例輸入：
6 7
0 1 1 0 1 1 0
0 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 0 0 1
1 1 0 0 0 1 0
1 1 0 1 1 0 0
0 0
範例輸出：
12
解題思維：
先對該分布圖中的每個點，求出整行（以整列為基準也可以，但是下面的所有動作皆須行列互換）到該位置為止最長的連續土地區間長度。在此以上方為起始點：
0 1 1 0 1 1 0
0 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 0 0 1
1 1 0 0 0 1 0
1 1 0 1 1 0 0
可以看到藍色 0 的位置往上延伸即停止，無法繼續延伸，所以長度為 1 ；而紫色 0 則是可以再往上延伸兩格，因此區間長度為 3 。其他例子以此類推。

將每個位置的區間長度都求出來之後。例如上圖會變為：
1 0 0 1 0 0 1
2 1 1 2 1 0 2
0 2 2 3 2 1 0
1 0 3 4 3 2 0
0 0 4 5 4 0 1
0 0 5 0 0 1 2
取其中的一列，例如 0 0 5 0 0 1 2 ，從左到右到表可以往上 0 單位、 0 單位、 5 單位、 0 單位、 0 單位、 1 單位、 2 單位。會長的像下面這樣子：
　　囗　　　　
　　囗　　　　
　　囗　　　　
　　囗　　　囗
　　囗　　囗囗
－－－－－－－
０１２３４５６
其中最大的矩形為第 2 行那一整條，面積 5 單位。

再往上一列，0 0 4 5 4 0 1：
　　　囗　　　
　　囗囗囗　　
　　囗囗囗　　
　　囗囗囗　　
　　囗囗囗　囗
－－－－－－－
０１２３４５６
當中，最大的矩形區域為紫色那塊，面積 4 × 3 ＝ 12 單位。

以此類推……最後可以推出這個分布圖中最大的矩形面積即是 12 單位。

因此，當做完每個位置的區間長的預處理之後，窮舉每一列的情形去求最大矩形即可。而最大的矩形的求法，可以參見以前的文章。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#動態規劃（Dynamic Programming）#堆疊（Stack）
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

更多創作

追蹤 創作集
其他創作
作品資料夾