17973 Takio的滑板鞋
时间限制:1000MS 内存限制:65535K
提交次数:79 通过次数:15 收入:28
题型: 编程题 语言: G++;GCC;VC;
Description
某一天SCAU_ACM校队的Takio去了第二个城市打比赛
这里的人们称它为魅力之都
时间过的很快比赛已经打完
他想他必须要离开
当他正要走时他看到了一家专卖店
那就是他要的滑板鞋
他的滑板鞋时尚时尚最时尚
回家的路上他情不自禁
摩擦 摩擦
在这光滑的地上摩擦
月光下他看到自己的身影
有时很远有时很近
感到一种力量驱使他的脚步
有了滑板鞋天黑都不怕
一步两步一步两步
一步一步似爪牙
似魔鬼的步伐
Takio想知道他是否能找出一条回家的路径,使得他回家步伐的步长为一步两步一步两步……,若能,Takio则可解锁成就“魔鬼的步伐”。
Details:
1.第奇数歩的步长为一步,第偶数歩的步长为两步,步数从1开始,第一步的步长为1,且Takio到家时的最后一步的步长必须为2(回家路径上的步长为1212……12)
2.已经过的位置不能再次经过。
3.不能经过或踩到障碍上。
4.若当前歩的步长为2,则需向同一方向移动两步。
输入格式
有多组测试数据(≤20)
每组测试数据的第一行是两个正整数n, m(1 <= n, m <= 8),代表平面区域的大小。
每组测试数据的第二行到第n + 1行是一个矩阵,代表二维平面的布局,s为Takio现在所在的位置,t为Takio的家,#为障碍,*为可到达区域
输入以EOF结束。
输出格式
对于每组测试数据,输出一行,若Takio可解锁成就“魔鬼的步伐”则输出”Yes”,否则输出”No”。
输入样例
5 7
######*
#***s*#
**#***#
t#*#**#
*****#*
5 7
######*
****s*#
**#***#
t#*#**#
*****#*
输出样例
No
Yes
做题思路
这是一道很经典的深搜题,没有用到剪枝是它成为水题的一大原因,下面讲讲思路。
首先,我们需要扫图:可以用矩阵来储存(因为边界问题,矩阵需要开大两个单位,不然扫到边界会报错) 扫到#记录是0 扫到*和s和t都记录是1 然后用四个变量记住起点和终点的坐标。(扫图是很关键的,建议自己做完扫图后用输出语句检查自己的矩阵有没有打错)
然后我们开始深度搜索,从起点开始往它周围的四个方向各走一步(如果没有障碍),将它走到的位置的坐标和走的步数传去下一个递归里,然后开头加个判断,如果坐标和步数符合终点要求就返回1,然后输出答案,如果不是的话,我们继续开始判断,会不会到了终点可是步数为1,这样我们就要返回0,代表这样走不行。然后我们通过上层递归传过来的步数和位置判断下一步要怎么走,记住,如果我们要走两步,两步都要判断是畅通的,而且两步的方向是不能改变的,再用新到的位置和走的步数进行传递,直到最后递归回来。 PS:记住走过的地方要暂时把点删掉,等递归回来后再把点复原,不然会重复走。
至于那个表要怎么打出来,我是这样的,我先用一个while(1)做来回循环,然后最后那里加了一个if((s=gechar())==EOF) break;就可以实现不限次读取图了,然后用flag来记录找到路没有,方便打印。
代码
|
|
|
|
写在最后
这题只考到了普通dfs,而再深一层就是记忆化dfs了,因为有了记忆化,时间会进一步缩短,当然难度也会大一丢丢。