Lost in the City

小Hi獨(dú)自一人來(lái)到了一個(gè)H市，卻不小心迷路了。幸運(yùn)的是小Hi有一張這個(gè)城市的地圖，所以他打算先確定自己在哪。H市的地圖是一塊NxM的矩陣，左上角為(1,1)。每一個(gè)單元格會(huì)用字符表示該處的建筑物：'.'表示空地，'P'表示公園，'H'表示住宅，'S'表示道路，'M'表示商業(yè)建筑，'G'表示政府建筑，'T'表示樹(shù)林等等。小明觀察了以自己為中心的3x3區(qū)域建筑情況，他想知道自己現(xiàn)在可能身處于地圖的哪個(gè)位置。

算法分析

該題的考察點(diǎn)為字符串處理，以及基本的數(shù)組旋轉(zhuǎn)。

根據(jù)題目的信息，我們所要做的是一個(gè)二維的字符串匹配。判定一個(gè)?3x3?的模板?p?是否在母串?s?中出現(xiàn)。

對(duì)于題目給定的數(shù)據(jù)范圍?n,m ≤ 200?，直接采用暴力枚舉匹配的方法也是能夠通過(guò)的，其代碼如下：

for?startX?=?1?..?n?-?2
????for?startY?=?1?..?m?-?2
????????flag?=?true;
????????for?i?=?0?..?2
????????????for?j?=?0?..?2
????????????????if?(p[i][j]?!=?s[startX?+?i][startY?+?j])
????????????????????flag?=?false;
????????????????end?if????
????????????end?for
????????end?for
????????if?(flag)?
????????????startX?+?1,?startY?+?1?is?answer?//?因?yàn)樾i處于?3x3?地圖的中央
????????end?if
????end?for
end?for

但在本題中，小Hi并不知道自己的朝向，所以母串?s?和模板?p?的方向可能并不是對(duì)應(yīng)的。

因此我們需要對(duì)模板?p?進(jìn)行旋轉(zhuǎn)，將其所有可能的方向都和母串?s?進(jìn)行匹配。

我們考慮旋轉(zhuǎn)90°的情況下，模板?p?和新的?p'?有何關(guān)系：

(0,0)?(0,1)?(0,2)???????(2,0)?(1,0)?(0,0)
(1,0)?(1,1)?(1,2)??-->??(2,1)?(1,1)?(0,1)
(2,0)?(2,1)?(2,2)???????(2,2)?(1,2)?(0,2)

通過(guò)觀察我們可以知道：

p'(i,j)?=?p(2-j,?i)

因此我們可以得到旋轉(zhuǎn)90°的函數(shù)：

//?對(duì)?p?進(jìn)行90°旋轉(zhuǎn)
rotate(p):
????for?i?=?0?..?2
????????for?j?=?0?..?2
????????????p'[i][j]?=?p[2?-?j][i];
????????end?for
????end?for
????return?p'

在該旋轉(zhuǎn)函數(shù)的基礎(chǔ)上，我們可以得到旋轉(zhuǎn)90°，180°，270°的結(jié)果：

p_rotate90??=?rotate(p)
p_rotate180?=?rotate(p_rotate90)????//?對(duì)90°再旋轉(zhuǎn)90°
p_rotate270?=?rotate(p_rotate180)???//?對(duì)180°再旋轉(zhuǎn)90°

因此我們的代碼改變?yōu)椋?/p>

for?startX?=?1?..?n?-?2
????for?startY?=?1?..?m?-?2
????????flag?=?false;?//?假設(shè)不匹配
????????//?是否和模板或旋轉(zhuǎn)之后的模板匹配
????????flag?=?check(s[startX?..?startX?+?2,?startY?..?startY?+?2],?p)?
????????flag?=?flag?|?check(s[startX?..?startX?+?2,?startY?..?startY?+?2],?p_rotate90)
????????flag?=?flag?|?check(s[startX?..?startX?+?2,?startY?..?startY?+?2],?p_rotate180)
????????flag?=?flag?|?check(s[startX?..?startX?+?2,?startY?..?startY?+?2],?p_rotate270)
????????if?(flag)?
????????????startX?+?1,?startY?+?1?is?answer?//?因?yàn)樾i處于?3x3?地圖的中央
????????end?if
????end?for
end?for

由于有多解的時(shí)候我們需要輸出字典序最小的位置。而按照我們的枚舉順序，枚舉到的第一個(gè)數(shù)一定就是字典序最小的位置，因此當(dāng)我們找到第一個(gè)合法解時(shí)，就可以直接輸出并退出我們的循環(huán)。