農夫過河問題 C 語言 BFS 求解：位掩碼狀態空間與邏輯錯誤修正

問題建模

• 4 個實體：農夫(bit3)、狼(bit2)、白菜(bit1)、羊(bit0)。
• 狀態用 4-bit 整數表示（0~15），0=全在左岸，15=全在右岸。
• 安全條件：農夫不在時，狼羊或羊白菜不能同岸。

關鍵錯誤

原代碼狀態轉移行：

newlocation = location ^ (0x00 | movers);  // 錯誤

0x00 導致農夫位(bit3)不翻轉，實際應翻轉農夫+被攜帶物：

newlocation = location ^ (0x08 | movers);  // 正確：0x08 = 1000b (農夫位)

BFS 完整流程

1. 隊列初始狀態 0，route[0]=0。
2. 出隊狀態，枚舉 movers = 1,2,4,8（農夫單獨/帶狼/帶羊/帶白菜）。
3. 檢查農夫與攜帶物同岸 (location&0x08) == (location&movers)。
4. 計算新狀態，安全且未訪問則入隊、記錄前驅 route[new]=loc。
5. 到達 15 回溯輸出路徑。

輸出示例

the revers path is:
the location is:15
the location is:11
the location is:9
the location is:13
the location is:5
the location is:7
the location is:3
the location is:0