题意分析
小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
由于有多解的时候我们需要输出字典序最小的位置。而按照我们的枚举顺序,枚举到的第一个数一定就是字典序最小的位置,因此当我们找到第一个合法解时,就可以直接输出并退出我们的循环。
结果分析
作为该场比赛的第一题,有将近一半的选手都通过了本题。
本题几乎没有什么trick,只要能够考虑清楚如何对模板进行旋转,就能够顺利通过该题。
找到和中心匹配的位置,然后看周围一圈是否相同,你的算法不怎么科学。
感觉绕圈比较方便~~~不用转来转去,头晕~~~