用0表示在左岸,1表示在右岸.
用頂點序號的二進制碼的0位表示農(nóng)夫,1位表示狼,2位表示羊,3位表示菜.
那么,總共可能有16個頂點0-15.頂點0表示全在左岸,頂點15表示全在右岸.
當(dāng)然有些頂點是不允許存在的,比如頂點3,表示農(nóng)夫和狼在右岸,羊和菜在左岸,羊會吃掉菜.你要把所有這類的頂點去掉.
在剩下的頂點中,你要找出所有的可能的邊.比如頂點5表示農(nóng)夫和羊在右,狼和菜在左,頂點4表示羊在右,那么就存在頂點5到頂點4的有向邊.
至此,圖已構(gòu)造完畢,問題就轉(zhuǎn)換成找到一條從頂點0到頂點15的合理路徑.