娱乐 每 日 算 法 挑 战 （大嘘）【第0x16期】

[Mr.K 018]

第22期！

可怜的MrK-019又被汉化组抓住了，他能不能摆脱被吃的命运呢？救救019 保护019，人人有责

第22期 汉化组的吃人陷阱2

汉化组布下的上一个吃人陷阱没能成功地吃到MrK-019，这一次汉化组升级了他们的陷阱！

汉化组布下的陷阱和上一次的差不多。一种格子迷宫，只有一个出口。迷宫大概是这样的：

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

如图所示，图上标为#的地方都是墙，标.的地方都是可以走的部分。MrK-019初始所在的地方也是可以走的部分。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 10 
######
#K...#  
###..#  
#S...#  
######

样例输出2

No

 

[yhz012]

反正先跑一遍1的算法不亏，同样的道理，如果最短路径d < s,或者d - s是奇数，就可以直接放弃治疗了

对于d-s是偶数的情况那就需要额外判断是否存在指定长度的迂回路径了……

感觉可以考虑用类似iterative dfs的想法解？就是限制dfs深度在s上，如果求到了K-S路径，那就能跑，求不到就凉了

不对，似乎有问题，除非同时维护多个closed list，否则idfs也一样会出现incomplete的问题

 

所以还是考虑迂回路径似乎更靠谱一点

如果迂回路径存在，那首先这个图要存在环，所以不存在环的情况可以直接打死了

（总觉得这回问题比我想的要难了……我甚至怀疑是NP级别的

自信点，把觉得删了。我可以不断增加s大小，这样这个问题可以用来找到一个图里的最长简单路径。已知最长简单路径是NPC，这问题没跑了

五月 7, 2020，由yhz012修改

[PhoeniXLL]

快请布鲁特·福斯先生过来

[yhz012]

1 小时前, PhoeniXLL 说道:

快请布鲁特·福斯先生过来

艹我想了半天这是谁，然后我想起来了brute force

 

↓我真的以为有现成的算法来判定无向图中2顶点间是否存在给定长度路径的算法，然后百度搜到是字符串匹配算法，就很迷惑

五月 7, 2020，由yhz012修改

[Mr.K 018]

5 小时前, yhz012 说道:

反正先跑一遍1的算法不亏，同样的道理，如果最短路径d < s,或者d - s是奇数，就可以直接放弃治疗了

对于d-s是偶数的情况那就需要额外判断是否存在指定长度的迂回路径了……

感觉可以考虑用类似iterative dfs的想法解？就是限制dfs深度在s上，如果求到了K-S路径，那就能跑，求不到就凉了

不对，似乎有问题，除非同时维护多个closed list，否则idfs也一样会出现incomplete的问题

 

所以还是考虑迂回路径似乎更靠谱一点

如果迂回路径存在，那首先这个图要存在环，所以不存在环的情况可以直接打死了

（总觉得这回问题比我想的要难了……我甚至怀疑是NP级别的

自信点，把觉得删了。我可以不断增加s大小，这样这个问题可以用来找到一个图里的最长简单路径。已知最长简单路径是NPC，这问题没跑了

这个题数据量没那么大，我记得正解就是布鲁特·福斯算法（

[yhz012]

13 小时前, Mr.K 018 说道:

这个题数据量没那么大，我记得正解就是布鲁特·福斯算法（

噗，那最坏情况就给每个路径单独维护一个closed list，然后dfs限定最大深度s跑起来就完了（

[Mr.K 018]

3 小时前, yhz012 说道:

噗，那最坏情况就给每个路径单独维护一个closed list，然后dfs限定最大深度s跑起来就完了（

甚至不用维护closed list，反正不上多线程，直接在地图上修改就行了