娱乐 每 日 算 法 挑 战 【第0x12期】

[Mr.K 018]

第18期来啦！

第18期 汉化组的吃人陷阱1

MrK-019有一次不小心暴露了自己会中日英三语和视频剪辑的事实，现在某个汉化组已经布下了天罗地网，只要时机一到就要把他收入囊中，调教成无情的汉化机器！

已知汉化组布下的天罗地网是一种格子迷宫，只有一个出口。迷宫大概是这样的：

######
#K...#  
####.#  
#S...#  
######

如图所示，图上标为#的地方都是墙，标.的地方都是可以走的部分。MrK-019初始所在的地方也是可以走的部分。MrK-019一秒可以走一格。出口只在某一秒开放，平时都是不能走的墙；如果MrK-019在出口开放的那一秒到达出口，他就能逃脱汉化组的吃人陷阱，否则就会被抓住吃掉（指调教成无情的汉化机器）。同时，由于汉化组的人就在后面穷追不舍，MrK-019必须不停地移动才行！

MrK-019能不能从汉化组的吃人陷阱里逃出来呢？

输入

第一行是三个整数m,n,s，分别表示迷宫的长和宽，以及出口在第几秒开放。

接下来是一个m*n的字符矩阵，表示汉化组设下的迷宫。格式见题干和输入样例。

输出

如果MrK-019能逃出来，就输出一行Yes，否则输出一行No。

样例输入1

5 6 8
######
#K...#  
####.#  
#S...#  
######

样例输出1

Yes

样例输入2

5 6 9
######
#K...#  
####.#  
#S...#  
######

样例输出2

No

四月 30, 2020，由Mr.K 018修改

[Mr.K 018]

1 小时前, 随性而为 说道:

//这里我觉得只要提前到了终点处就算没开也应该要等在那啊，不应该还在失了智的左右横跳等出口啊

终点没开之前是墙，而且不允许停（那样就太没意思了（笑））

而且，这个DFS是没法找到最短路径的，会导致有些能yes的例输出no

四月 30, 2020，由Mr.K 018修改