POJ 3083 Children of the Candy Corn

题意

对于一个入口和出口都在边界的迷宫,有两种一定能保证走出迷宫的方案,想象你自己站在迷宫的入口,你可以一直让左手扶着墙,贴着墙走,这样最后一定会走到终点。你也可以一直让右手扶着墙,贴着墙走,最终也一定会到达终点。现在要你模拟这两种策略,分别输出这样走要经历的步数,同时再算出不限于上述策略的走出迷宫的最短路方案。

思路

对于最短路,只要使用常规的BFS就可以解决。难点在于如何模拟左手扶墙和右手扶墙。如果是以左手扶墙来遍历迷宫的话,其实是相当于每一次都先尝试去走当前面朝方向的左边,若无法走,尝试直行,还不行的话,再尝试右行和上行。每一次行走,你要想想自己身处迷宫之中,并且根据你的行走动作来改变自己的朝向,模拟这个过程就是本题的难点。

有一种比较聪明的实现方式,就是把原来的行进向量(dir),也当成朝向向量来用,往左行走相当于朝向向量左转,直行相当于无旋转,右行相当于向右旋转,下行相当于两次右旋。每一次前进时把旋转完的朝向向量当行进向量用就可以了,下一次还是按照上面所述的循环操作。

本题还有一个技巧,你只需要实现扶一边墙行走,因为从起点扶一边墙走到终点相当于从终点扶另一边墙走到起点,所以你在第一次行走完之后,只要交换起点终点的’S’和’E’,然后再执行一次从”原终点”到”原起点”的行走,就可以了。

代码

 

1 Comment

  1. […] POJ 3083 Children of the Candy Corn […]

    Reply

Leave a Reply

Scroll to top