1108.txt

集合了SOJ（四川大学ACM在线评测系统）众多经典题目的详细解题报告

1108 holedox moving
    这个题是一个比较经典的广度搜索题，其最与众不同的地方是搜索元素从一个点变成了一条线，从而加大了搜索过程中的状态保存的难度。
    最开始看到这个题时，觉得就是迷宫方面的类似问题，只要将蛇每移动一步后的地图状态重新刷新就可以，但在写搜索的过程中，遇到几个问题：
    1.地图的变化情况不好表示
    2.每走一步后的步数是否最优，即蛇是不是在向着出口方向移动不能判断，因而造成了很多重复的搜索情况。
    解决方法：
        对蛇到达任何一个点时，整条蛇所处的状态作为一个单独变量进行保存，即蛇以不同姿态到达同一点被认为是不同的一种方案。开一个数组map[20][20][16*1024]，则map[i][j][k]表示蛇头在(i,j)点时，其蛇身所处的姿态为map[i][j][k]由于每次的蛇的移动只需要考虑头和尾的状态变化，所以可以用相对位置来表示蛇各段身体与蛇头的位置从而表示出整条蛇的姿态，上，下，左，右分别用2位二进制数来表示，则最多表示一条蛇需要14位二进制数，蛇移动时利用二进制数的左，右移来处理，再利用广度搜索即可。
    注：此题解法还有几种，如liulike的图论方法及比较有难度的深度搜索等