UVa 12192 Grapevine

本題題目連結

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

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