ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e575: 10908 - Largest Squares 解題心得

Not In My Back Yard | 2019-12-23 23:17:39 | 巴幣 0 | 人氣 514

題目連結(jié):


題目大意:
給定一正整數(shù) T (T < 21),代表有 T 筆測試資料。每筆測資的第一列給定三正整數(shù) M 、 N 、 Q (1 ≦ N 、 M ≦ 100 , Q < 21),代表接著有 M 列、每列 N 個(gè)字元,代表一 M × N 的地圖內(nèi)容。再接著有 Q 列,每列代表一筆詢問。

每列給定兩正整數(shù) r 、 c ,代表要詢問:
以第 r 列第 c 個(gè)字元為中心,以該中心建立一個(gè)正方形,使得正方形內(nèi)部的所有字元皆相等。試問,最大的正方形之邊長為何?



範(fàn)例輸入:
1
7 10 4
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
1 2
2 4
4 6
5 2


範(fàn)例輸出:
7 10 4
3
1
5
1


解題思維:
可以看到邊長一定是奇數(shù),才會(huì)有中心。

對於每一筆詢問直接漸漸擴(kuò)大正方形的邊長即可。一開始只有中心,接著判斷其周遭八格,再判斷更外圍的十六格……以此類推。直到碰到地圖邊界,或是該範(fàn)圍有字元跟中心字元不一致。前一個(gè)判斷的範(fàn)圍之長度 ÷ 4 即是所求的正方形最大可能邊長。

至於擴(kuò)張後的範(fàn)圍,可以中心座標(biāo) x 、 y 偏移量 i 決定。設(shè)該範(fàn)圍的最左上角座標(biāo)為 x - i 、 y - i (例如中心周遭的八格,其左上角為 x - 1 、 y - 1),則最右上角、右下角、左下角分別為 (x + i 、 y - i)(x + i 、 y + i)(x - i 、 y + i)。因此可以用四個(gè)迴圈(可以統(tǒng)一集合成一個(gè)),分別從四個(gè)角落開始往右、往下、往左、往上去跟中心的字元判斷。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創(chuàng)作集

作者相關(guān)創(chuàng)作

更多創(chuàng)作