為生存而奔跑

在漆黑的夜里，四位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，四個人一共只帶了一只手電筒，而橋窄得只夠讓兩個人同時過。如果各自單獨過橋的話，四人所需要的時間分別是1、2、5、8分鐘；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設計一個方案，讓這四人盡快過橋。

    過橋問題詳細的描述與解決方案請閱讀《過橋問題——經典智力題推而廣之五》,共7個小節，作者講述的非常細致。

    結論我給再敘述一下:

以下是構造N個人(N >= 1)過橋最佳方案的方法：

1)如果N=1或者N=2，所有人直接過橋。

2)如果N=3,由最快的人往返一次把其他兩人送過河。

3)如果N>=4,設A，B為走的最快的和次快的旅行者，過橋所需時間分別為a,b；而Z,Y為走得最慢的和次慢的旅行者，過橋所需時間分別為z,y。那么

當2b>a+y時，使用模式一將Z和Y移動過橋

當2b<a+y時，使用模式二將Z和Y移動過橋

當2b=a+y時，使用模式一或者模式二將Z和Y移動過橋。

這樣問題就變成了N-2個旅行者的情形，遞歸解決即可。

注：這里的模式1指的是A將Z送過橋，然后返回，再把Y送過橋，再返回；模式2指的是A和B先過橋，然后A返回，Y和Z過橋，然后B返回

1. pku 1700 Crossing River (pku 3404 Bridge over a rough river)

就是最樸素的過橋問題，問最少所需時間

2. pku 2573 Bridge

在1的基礎上加上過橋所需要的步驟

3. zju 1579 Bridge 

這里要用long long 真惡

4. hit 2540 Only One Boat

這個題目是過橋問題的變種,題目的意思就是有N隊夫妻,現在要過河，但是只有一條船，并且船每次只能載兩個人。要求每一個妻子不能在丈夫不在的情況下與其他男人在一起，無論是船上還是岸上都不可以。問最少的次數使得所有人過河，并打印具體的步驟(spj)。

這個問題最少次數其實是固定的，不難推出如果有n隊夫妻，那么全部過河的最少次數是5*n-3。（這個原因我請教了這個題目的作者，他的意思是最優的策略一定是兩個人坐船去彼岸，一個人坐船回此岸。因此最少次數是一定的)。知道了最少次數如何去打印具體步驟了，其實我們從樣例中3隊夫妻的說明中可以得到一些啟發，就是說經過若干步之后可以使得一對夫妻"Leave"。 例如3隊夫妻的時候，標號為1，2為第一對夫妻（奇數為男，偶數為女，下同）,標號為3，4為第二對夫妻，標號為5，6為第三對夫妻。那么由2，4首先坐船來到彼岸，然后2回去，2和6再來到彼岸回去，然后6回去，讓1，3過來，然后1和2離開，3回頭，3和5再過去，3和4離開，5回頭，5和6過河并離開。 現在轉換到n個人的情形。如果n=1或者2，那么很容易就能找到方案了，因此下面的情況針對n>=3的情況，我們可以先讓2n和2n-2過河，然后2n回來。(注：這個時候所形成的局面是此岸有n-1對夫妻和一個丈夫，彼岸有一個該丈夫的妻子）。下面2n和2n-4過河，然后2n-4回來，2n-1和2n-3過河，2n和2n-1 離開，2n-3返回。（注：這個時候的局面是此案有n-2對夫妻和一個丈夫，彼岸有一個該丈夫的妻子）?？梢钥闯鲞@是一個遞歸的過程。下面實現就簡單了。

5. zju 2288 Across the River

題目大意: n個男生和m個女生過河.只有一只船,船每次最多裝k人且滿足如下條件:

任何時候岸邊(包括此岸和彼岸)和船上要么沒女生.否則女生不比男生少，問最少要渡幾次才能使得所有人渡河完畢。

這個題目如果沒有說要求彼岸也滿足這個要求（即女生不比男生少，或者沒有女生），我們可以利用貪心算法解決。

可以總是先把男生給送到彼岸，然后剩下來的部分都是盡量在滿足條件的情況下把男生往船上放，然后每次把船從彼岸送回來的人最好是女生。這樣可以使得結果次數最少。

但是現在要求的是此案和彼岸都必須滿足條件，這樣的話我們就只能bfs搜了。數據量不算大

 TopCoder SRM 146 DIV2 1000代碼：