奇偶剪枝

系统管理员 2024-02-18 23:05 48阅读 0赞

**奇偶剪枝**

**【问题描述：】**

给定一个N\*M的迷宫以及起点和终点，迷宫中有一些障碍无法穿过，问能否不重复也不停留地在刚好一共走T步出迷宫。

**【问题分析：】**

先来看下这张图片：

![70][]

也就是说当要走偶数步而规定的步数是奇数，或者要走奇数步而规定的步数是偶数，都是不可能到达的，**如果要想到达，则要走的步数和规定的步数的奇偶性应该一致**。又可知，**奇偶性一致的两个数的差或者和都是偶数**。（下面有大用处）（引自[https://blog.csdn.net/i1020/article/details/54918472][https_blog.csdn.net_i1020_article_details_54918472]）

由此，可以得出如下式子：

设t为起点到终点的步数，起点为s,终点为e,s->e的最短距离为p，那么**有****t-p****为偶，则在****t****步恰好到达终点****e**.

下面来对上面做出证明。

**证明：****t-p****为偶，则在****t****步恰好到达终点****e.**

要想在第t步到达终点那么有t = p + extra

整理得t - p = extra.

即**证明****extra****为偶**

下面来证extra为偶，分四种情况（结合上图）：

1.  起点s为0，终点e为0，此时p为偶。
2.  起点s为1，终点e为1，此时p为偶。
3.  起点s为0，终点e为1，此时p为奇。
4.  起点s为1，终点e为0，此时p为奇。

上面的情况可整理为两种情况：

1.  p为偶（起点终点相同）
2.  p为奇（起点终点不同）

*  **对于第一种情况：**

先走随便走p到达点m,因为p为偶，所以m与s相同且与e相同，将m作为新的起点s1,终点为e,则t1 = t - p,式子变为t1 = extra + p1;

重复上述步骤，直到tn = pn(pn为当起点为sn终点为e时的最短路径长度)，即第n步到达点e。得出式子extra = 偶数 \+ 偶数 \+ 偶数\+。。。\+偶数 =>偶数。

*  **对于第二种情况：**

先随便走p到达点m，因为p为奇数，所以m与s不同，与e相同，将m作为新的起点s1，终点为e，t1 = t - p,问题转为了第一种情况。得出式子extra = 偶数 \+ 偶数 \+ 偶数\+。。。\+偶数 =>偶数。

**得出结论**

设t为起点到终点的步数，起点为s,终点为e,s->e的最短距离为p，那么有t-p为偶，则在t步恰好到达终点e。

证明比较粗糙，欢迎大家修改探讨。

一道奇偶剪枝的题目[http://acm.hdu.edu.cn/showproblem.php?pid=1010][http_acm.hdu.edu.cn_showproblem.php_pid_1010]

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/590754006563470e916fd521c21b5f23.png
[https_blog.csdn.net_i1020_article_details_54918472]: https://blog.csdn.net/i1020/article/details/54918472
[http_acm.hdu.edu.cn_showproblem.php_pid_1010]: http://acm.hdu.edu.cn/showproblem.php?pid=1010