天天看點

HDU 1010 Tempter of Bone DFS + 奇偶剪枝

奇偶剪枝:

對于從起始點 s 到達 終點 e,走且隻走 t 步的可達性問題的一種剪枝政策。

如下列矩陣 :

HDU 1010 Tempter of Bone DFS + 奇偶剪枝

從任意 0 到達 任意 0,所需步數均為偶數,到達任意 1 ,均為奇數。反之亦然

是以有,若s走且隻走 t 步可到達e,則必有t >= abs(s.x - e.x) + abs(s.y - e.y),且 (t&1) == ((abs(s.x - e.x) + abs(s.y - e.y))&1)。

否則必不可達。

繼續閱讀