奇偶剪枝学习笔记

ans=t-time-abs(dx-x)-abs(dy-y); if(ans<0||ans&1) return;

说了这么多，再总结一下吧！

什么是奇偶剪枝？

把矩阵看成如下形式：

所以当遇到从 0 走向 0 但是要求时间是奇数的或者 从 1 走向 0 但是要求时间是偶数的，都可以直接判断不可达！

比如有一地图：

S..................D

要求从S点到达D点，此时，从S到D的最短距离为s = abs ( dx - sx ) + abs ( dy - sy )。

如果地图中出现了不能经过的障碍物：

S..XXX.X...X.XXX...D

此时的最短距离s' = s + 4，为了绕开障碍，不管偏移几个点，偏移的距离都是最短距离s加上一个偶数距离。

就如同上面说的矩阵，要求你从0走到0，无论你怎么绕，永远都是最短距离(偶数步)加上某个偶数步；要求你从1走到0，永远只能是最短距离(奇数步)加上某个偶数步。

这里我来讲一下搜索中要用到的奇偶剪枝的原理：

看张图，没障碍物#时，S到E的最短路长为6，但是当有障碍物时，就要绕行了

看这张图，黑色为最短路径，当他绕行（红色加蓝色部分）时，其中蓝色部分其实还是最短路径部分平移来的，所以多走的步数也就是红色部分

对于红色部分我们可以分为两部分，一部分是远离最短路径的步数，另一部分是回到最短路径的部分，他们一定是对称的，所以多走的步数一定是偶数！！！

所以要是问走x步能否到达e，就算出最短路径长y，如果x-y是偶数就能到达，否则不能到达！