2.1過河智力游戲
（1）專案描述
游戲規則：一家6口（爸爸、媽媽、兩個女兒、兩個兒子）及警察和小偷要從河這邊
渡到河對岸。在河這邊僅有一艘小舢板可以把他們載到對岸。可是，只有爸爸、媽媽和警
察能夠駕船，不論成人與小孩，每程只能承載二人。在渡河程序中，你要避免以下三種情
況的發生：
（1）當警察與小偷分開時，小偷會傷害一家6口；
（2）當爸爸看見媽媽離開時，爸爸便會教訓女兒；
（3）當媽媽看見爸爸離開時，媽媽便會教訓兒子。
游戲的玩法參見guohe.swf。
要求學生給出一組過河的可行解
（2）解決思路
【資料結構建模】
一共八個人，每個人都有兩個狀態（左岸和右岸）。我們把八個人在左岸的狀態記為
[0,0,0,0,0,0,0,0]，都在右岸時記為[1,1,1,1,1,1,1,1]。那么，本專案其實就是要尋找一個從
[0,0,0,0,0,0,0,0,0]到[1,1,1,1,1,1,1,1]的解。
這個狀態我們其實可以開辟一個8個元素的陣列。另外還需要設定一個變數代表船的
狀態。因為還要列印結果，所以在搜索的程序中還需要一個結構體陣列存盤每次渡河的人
是誰（可能是一個人，也可能是2個人），當然，也可以建立2個一維陣列代替結構體陣列。
接下來可以選擇深度優先搜索或者寬度優先搜索來進行搜索，每個狀態的限制條件根
據題意可以得出。
最后遍歷存盤渡河人員的陣列，并列印出結果。
其實每個人的狀態（包括船的狀態都是0或者1），所以其實用一個int型就可以了。
狀態轉移全部使用位運算。
【建立模型】
使用2的整數次冪表示不同人，所以使用一個整數表示當前的局面，255為初始，0
為結束。
{POLICE=0x80,THIEF=0x40,DAD=0x20,BOY1=0x10,BOY2=0x8,MOM=0x4,GIRL1=0x
2,GIRL2=0x1,ALL=0xff,OK=0};
（3）問題擴展
將陣列存盤狀態，變換為用一個位元組來表示各個人的狀態，然后采用位運算方式進行
升級。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/14272.html
標籤：C語言
上一篇：proteus仿真 LED交通燈