奇偶剪枝

描述

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

s
\|
\|
\|
+	—	—	—	e

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

s	—	—	—
	—	—	+
\|	+
\|
+	—	—	—	e

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

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

結論

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

返回，false；

反之亦反。

原理補充

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

還是以這個為例子吧，現在我把矩陣填滿 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	1	0

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

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

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

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

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

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

s	—	—	—
	—	—	+
\|	+
\|
+	—	—	—	e

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

在來一個例2吧，

s	—	—故危和	—
	—	—	+
\|	+
\|		+	—	e
+	—	—

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

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

再來看我給的 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	1	0

設左上角坐標為（1，1），右下角坐標為（5，5）.

那么我們給的例1，

起點 s 的坐標為（1，1），此點為“0”；

終點 e 為（5，5），此點為“0”。

所以t=8，為偶數。

現在我們再倒過來看，從終點(也就是 e )出發，把最短步數 t=8 耗費掉，不妨這樣走，

s			+
		+	—
		\|
	+	—
	—	—	e

如圖所示從 e （5，5）耗費 8 步走到了（1，5）點。

因為是從 0 走偶數承紋霉芝步，所以走到的坐標也一定是 0 ，就像這裡的（1，5）點是 0 一樣。

這是一個遞歸的過程，首先如果從0開始，目的地也是0，那末其中的最短距離t必然是個偶數，可其中有可能有障婆鍵恥礙物或需要繞彎的情況，那末我們就現將最短距離t用於繞彎，從開始的0，走t步不管怎么走都只能到0，而這個0到終點0的最短路徑t也必然是偶數，一直遞歸下去，直到你繞夠了到達終點，這中間你額外的步數都是偶數。

注意到，（1，5）點和起點 s （1，1）都是 0，也就是說，這個 extra 必然是偶數！贈提譽

再看例2，同樣從終點 e 開始耗費 t=7 步，

則所到的點一定是 0 (不管她在哪裡)，再從這個點回到起點 s ，所用的 extra 也必然是個偶數！

所以無論如何，sum= t + extra ( extra>=0 ) 中的 extra 都是一個偶數

那么我們就可以用公式 t-[abs(ex-sx)+abs(ey-sy)] 計算出extra是否為偶數來判斷當前點能否恰好在這么多步到達終點了。

有的同學可能會說以 1 為起點呢。。其實是一樣的啦，自己去搗鼓吧。

現在明白了么。。那么我再給個經典的實例吧，自己去試著做一下 ZOJ 2110 或者 HDU 1010。

奇偶剪枝

基本介紹

描述

結論

原理補充

相關詞條

熱門詞條