Lost in the City

小Hi独自一人来到了一个H市，却不小心迷路了。幸运的是小Hi有一张这个城市的地图，所以他打算先确定自己在哪。H市的地图是一块NxM的矩阵，左上角为(1,1)。每一个单元格会用字符表示该处的建筑物：'.'表示空地，'P'表示公园，'H'表示住宅，'S'表示道路，'M'表示商业建筑，'G'表示政府建筑，'T'表示树林等等。小明观察了以自己为中心的3x3区域建筑情况，他想知道自己现在可能身处于地图的哪个位置。

算法分析

该题的考察点为字符串处理，以及基本的数组旋转。

根据题目的信息，我们所要做的是一个二维的字符串匹配。判定一个 3x3 的模板 p 是否在母串 s 中出现。

对于题目给定的数据范围 n,m ≤ 200 ，直接采用暴力枚举匹配的方法也是能够通过的，其代码如下：

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 // 因为小Hi处于 3x3 地图的中央
        end if
    end for
end for

但在本题中，小Hi并不知道自己的朝向，所以母串 s 和模板 p 的方向可能并不是对应的。

因此我们需要对模板 p 进行旋转，将其所有可能的方向都和母串 s 进行匹配。

我们考虑旋转90°的情况下，模板 p 和新的 p' 有何关系：

(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)

通过观察我们可以知道：

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

因此我们可以得到旋转90°的函数：

// 对 p 进行90°旋转
rotate(p):
    for i = 0 .. 2
        for j = 0 .. 2
            p'[i][j] = p[2 - j][i];
        end for
    end for
    return p'

在该旋转函数的基础上，我们可以得到旋转90°，180°，270°的结果：

p_rotate90  = rotate(p)
p_rotate180 = rotate(p_rotate90)    // 对90°再旋转90°
p_rotate270 = rotate(p_rotate180)   // 对180°再旋转90°

因此我们的代码改变为：

for startX = 1 .. n - 2
    for startY = 1 .. m - 2
        flag = false; // 假设不匹配
        // 是否和模板或旋转之后的模板匹配
        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 // 因为小Hi处于 3x3 地图的中央
        end if
    end for
end for

由于有多解的时候我们需要输出字典序最小的位置。而按照我们的枚举顺序，枚举到的第一个数一定就是字典序最小的位置，因此当我们找到第一个合法解时，就可以直接输出并退出我们的循环。