vijos1656萌萌赶考

本文主要是介绍vijos1656萌萌赶考，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给定一个地图的起点和终点，地图上有一些点不能通过，问是否存在从起点出发到终点，经过每个点至多一次且路径长度恰好为t的路径

算法分析

很朴素的搜索，但是也是练剪枝的好题。
1假设起点坐标为（sx,sy)，终点坐标为(ex,ey)，给定时间为t,那么如果满足(sx+sy+t)与(ex+ey)，那么直接输出No，正确性显然
2如果地图中可以经过的点的个数小于t，那么直接输出No
3如果已经走到了终点，但是时间不等于t，那么剪枝
用了以上三个剪枝就可以AC了

另外这题有2个很坑的地方= =
1 题目没有说明”S”的意思，如果把S当做起点，在地图中找S那么只有10分
2 不能重复经过其他的点，但是可以重复经过起点一次（什么神奇的设定….

灵异事件

如果按右下左上的方向顺序搜索的话，耗时会比较大。。但是如果改成左上右下的顺序搜索的话，就可以秒杀此题= = 不知道是什么神奇的原理。。

附题目：

描述
绵羊爸爸一晚做了一个奇怪的梦，他梦见了萌萌十七岁的时候参加高考。萌萌所在的考点十分奇特，只有在规定的那1秒钟时刻才会开放（也就是说恰好到达考点，超过或时间未到都不能进入考点）。而萌萌从家里（萌萌的家在左上角）出去，在参加考试的途中可以在大街上走走（可以往上下左右任意方向走，不可以重复经过同一区域），但不能去娱乐场所。现在给你一张JS市的地图，以及从萌萌离开家到考点开放的时间，请你预测萌萌在绵羊老师的梦中能否成功参加这次神奇的高考？
格式
输入格式

输入数据包含多个测试点（不超过5个）。
每个测试点的第一行包含三个正整数N,M,Time(0 < N,M < 7; 0 < Time < 50)。接下来N行给出从萌萌家到考点的地图，每行包含M个字符。所有字符中仅会出现以下情况：
‘*’：表示普通道路；
‘D’：表示当地的考点（仅会出现一次）；
‘H’：表示娱乐场所；
左上角的方格内字符一定为’*’。注意：出发点一开始不算走过。
文件将以0 0 0作为结束。
输出格式

对于每一个测试点，你只需要输出’Yes’表示可以准时到达，反之则输出’No’。

这篇关于vijos1656萌萌赶考的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---