奇偶剪枝

描述

現假設起點為(sx,sy)，終點為（ex,ey），給定t步恰好走到終點，

如圖所示（“|”豎走，“—”橫走，“+”轉彎），易證abs(ex-sx)+abs(ey-sy)為此問題類中任意情況下，起點到終點的最短步數，記做step，此處step1=8；

如圖，為一般情況下非最短路徑的任意走法舉例，step2=14；

step2-step1=6，偏移路徑為6，偶數（易證）；

推廣之，若 t-[abs(ex-sx)+abs(ey-sy)] 結果為非偶數（奇數），則無法在t步恰好到達；

返回，false；

反之亦反。

鑒於很多同學對奇偶剪枝根本原理的興趣，所以hj決定再補充一下本詞條。

還是以這個為例子吧，現在我把矩陣填滿 0 和 1

我們現假設從 0 開始走，則不難證明，

從任意 0 走到任意 1 始終是奇數步；

從任意 0 走到任意 0 始終是偶數步；

引用描述里的“例子”， s 到 e 的最短步數為 t (當然你也可以理解成此時到終點剛好剩餘 t 步等等)。

則，我們從 s 到 e 的步數之和(或者說總距離)總可以表示成 sum= t + extra ( extra>=0 )，其中 extra 表示額外的步數。

比如“例子”裡面的，做例1吧

此時 t=8，sum=14，所以我們容易得到 extra=6。也就是說按照這個走法，需要在最短的步數上再走額外的 6 步(先不用太在意這些偏移是在什麼地方產生的)。

在來一個例2吧，

此時，t=7，sum=15，所以我們也容易得到 extra=8。

根據理科生的天性，由這兩個一般性的例子，我們很容易嗅察到 extra 都為偶數。先帶著疑惑，

再來看我給的 0 、1 矩陣。