網頁

2014年1月25日 星期六

UVa 12192 Grapevine

本題題目連結

題意:
  N為該矩形範圍的高,M為長,並輸入該範圍內每個數字,Q代表要測試幾次,每次給定L,U,在範圍內求出最大正方形的邊長,該正方形內的數字都要符合L<=H[i][j]<=U,也就是介於L和U之間。

想法:
  題目給的範圍內的數字是有限制的,同列右邊比左邊大,同行下面比上面大,因此隨便框出一個正方形,其左上角必定為最小,右下角必定為最大,所以我們只要確認左上角>=L,和右下角<=U是否滿足即可。那麼首先從每列開始,在同一列使用二分搜尋找出左上角,然後沿著對角線二分搜尋找出右下角,最後把每列找出的正方形選出邊長最大的即可。