11871NewLand..ppt

1 11871:New Land ★★★★☆ 題組：Problem Set Archive with Online Judge 題號：11871: New Land 解題者：施博修 解題日期：2011年6月8日 題意：國王有一個懶兒子，為了勞動兒子，他想了一個辦法，令他在某天早上開始走路，直到太陽下山前，靠走路所圍出來的一個矩形空地，均歸他所有。 國王領土中，難免有些岩石擋路，而國王的兒子卻不想在圍出來的空地中含有岩石，求出所能圍出的一塊最大矩形空地。 題意範例： 輸入： 整數T(共有幾個測資) 每個測資有一組M、N，代表了M rows, and N cols 接下來N行 每個整數代表 k, c, p1, p2, p3, ..., pk p1代表前p1行為type c p2代表接著p2行為opposite of c p3代表接著p3行為type c…and so on 輸出： 所含最大矩形的面積 輸入範例： 輸出範例： 圖解 解法：此題目為find largest rectangular問題 先用一個二維陣列儲存資料，接著將二維圖形切成直條(行)，再用DP的方式計算每一條直線(行)的Empty Interval高度。 接著對每一個橫條(列)，作為矩形的底線，並利用stack來算出矩形面積。 每個陣列元素均走訪過後，所得的Max Area即為解答。 解法範例： 集合每一條直線(共有N條)的Empty Interval高度，其所形成的二維陣列，接下來利用這個陣列以及stack方式求出最大面積矩形 討論： 因為對每一列都要利用stack求出利用該列為底的矩形面積，而每一列中每個元素都要走訪過一次 因此時間複雜度為O(M*N)。 * 以最後一列說明過程 1.一開始遇到高度2，此時stack為空，Push進stack，高度2、位置1 stack 2,1 stack 2.接著遇到高度4，因為42，Push進stack，高度4、位置2 2,1 stack 2,1 4,2 stack 3.接著遇到高度3，因為34，Pop，並計算面積4*(3-2)=4 2,1 4,2 stack 2,1 stack 3.Pop出來後，需要再次比較stack頂端值的高度與目前高度 因為32，Push進stack，但因為之前有pop過，因此存入位置必須是上次pop出來的位置，高度3、位置2 2,1 stack 2,1 3,2 stack 4.接著遇到高度2，因為23，Pop，並計算面積3*(4-2)=6 2,1 3,2 stack 2,1 stack 5.最後遇到高度0，因為02，Pop，並計算面積2*(5-1)=8 2,1 stack stack 5.Stack已經為空，且已進行到最後，跳出此列計算