奇偶剪枝-优化(ZOJ 2110 ， HDU 1010)
奇偶剪枝经典的实例， ZOJ 2110 ， HDU 1010
从1走向1的时候与0走向0的情况是一样的。
|
s
|
—
|
—
|
—
| |
|
—
|
—
|
+
| ||
|
|
|
+
| |||
|
|
| ||||
|
+
|
—
|
—
|
—
|
e
|
|
0
|
1
|
0
|
1
| 0 |
| 1 |
0
|
1
|
0
| 1 |
|
0
|
1
| 0 | 1 | 0 |
|
1
| 0 | 1 | 0 | 1 |
|
0
|
1
|
0
|
1
|
0
|
易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下起点到终点的最短步数。
所以，t-[abs(ex-sx)+abs(ey-sy)] < 0时候或者 t-[abs(ex-sx)+abs(ey-sy)]的结果为奇数时可直接判定无法在t步到达，
即t必须大于等于最短步数并且满足相应情况下的为奇为偶才继续之后的始点是否可以到达终点。
故此达成剪枝优化。