转跳到内容

每 日 算 法 挑 战 (大嘘)【第0x16期】


推荐贴

第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

 

链接到点评

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

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

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

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

 

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

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

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

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

,由yhz012修改
链接到点评
1 小时前, PhoeniXLL 说道:

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

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

 

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

,由yhz012修改
注释
ZERC ZERC 1.00节操 2333333333
链接到点评
5 小时前, yhz012 说道:

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

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

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

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

 

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

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

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

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

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

Mr.K 018在游玩时被热情的工作人员拉进主题公园,在参与游戏之后获得奖励2节操。

链接到点评
3 小时前, yhz012 说道:

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

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

Mr.K 018看指路牌的时候拾起一片古怪的叶子,被河童用1节操买來高兴地吃掉了

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款