典型的迷宫搜索，熟练掌握该题将具有里程碑式的意义！
每个block只能走一次
要求恰好某个给定的时间到达出口
1、一个迷宫，一个长方形大小的N,M
X 代表小够不能走
S 代表小狗初始位置
D 出口门的位置
。小狗可走的块
T 门在第T秒打开，小狗必须在第T秒到达(也就是走左T步后到)
At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second.
N，M，T
4 4 5
S.X.
..X.
..XD
问题分析:
是否存在从出发点到终点距离为time的路径
这道题很明显是搜索题,但是要经过剪枝,不然会超时.
若将这个地图看成是一张图,那么在n*m,时间t的情况从s点走到d点,经过t条边的路径数平均有900多条,每条长度为t,那么这个dfs的运行的时间就会达到T(900*t),比较极限的数据会使一个dfs能有几百万的复杂度,那么这个程序肯定是会超时的了.
它的规律是：0和1相间排列。仔细观察不难发现，当行号和列号同为奇数，或者同为偶数时，写0；否则，写1。
而且，从0的格子走1步，不管哪个方向，都会走到1的格子上。
于是我们得出这样的结论：
0->1 或 1->0 必定走奇数步，
0->0 或 1->1 必定走偶数步。
所以当我们遇到不满足上述两个结论的，可以推断它不能到达，所以中止搜索。
还有一种特殊情况，就是当地图上能走的点的个数（不包括起点）小于时间t的时候，显然不能到达，这时可以不用搜索，直接输出NO；
阅读(2512) | 评论(0) | 转发(0) |
