hiho一下第68周《Lost in the City》题目分析

3
0

题意分析

小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,只要能够考虑清楚如何对模板进行旋转,就能够顺利通过该题。

  • 找到和中心匹配的位置,然后看周围一圈是否相同,你的算法不怎么科学。

  • 感觉绕圈比较方便~~~不用转来转去,头晕~~~

  • 添加评论
  • reply

4 answer(s)

0

这样枚举太慢了吧。楼上那种方法较快,先考虑模版中心的元素是否一样,由于考虑方位的影响,需要进行4次比较匹配,但是选择的过程可以省去直接对应位置进行比较,这样可以省去选择的时间

0

这样枚举太慢了吧。楼上那种方法较快,先考虑模版中心的元素是否一样,然后看模板所在的那一行和3*3区域中间一行或中间一列,最后在考虑方位的影响

1

感觉Rotate可以用swap来写,就是通过6次交换p的元素来使模板p右旋90°(虽然并没有什么。用)

1

在书写最后一段伪代码时需要改为 flag = flag | check(),即flag或(or)上check()

write answer 切换为英文 切换为中文


转发分享