2.5　暴力求解法

本節(jié)選解習題來源于《算法競賽入門經(jīng)典（第2版）》一書的第7章。

習題7-1　消防車（Firetruck, ACM/ICPC World Finals 1991, UVa208）

輸入一個n（n≤20）個結(jié)點的無向圖以及某個結(jié)點k，按照字典序從小到大順序輸出從結(jié)點1到結(jié)點k的所有路徑，要求結(jié)點不能重復經(jīng)過。

【分析】

如果1和k不連通，直接DFS搜索路徑的話，一定會超時。而要判斷1和k是否連通，使用《算法競賽入門經(jīng)典（第2版）》第11.2.1節(jié)中介紹的并查集即可。

本題建圖時每個結(jié)點的鄰居可以使用set<int>存儲，這樣輸入之后自然就是排好序的。使用DFS從1開始搜索到k的所有路徑。因為結(jié)點不能重復經(jīng)過，所以要在搜索過程中對已經(jīng)經(jīng)過的結(jié)點進行判重。完整程序（C++11）如下：

習題7-2　黃金圖形（Golygons, ACM/ICPC World Finals 1993, UVa225）

平面上有k個障礙點。從(0,0)點出發(fā)，第一次走1個單位，第二次走2個單位，……，第n次走n個單位，恰好回到(0,0)。要求只能沿著東南西北方向走，且每次必須轉(zhuǎn)彎90°（不能沿著同一個方向繼續(xù)走，也不能后退）。走出的圖形可以自交，但不能經(jīng)過障礙點，如圖2.34所示。

輸入n、k（1≤n≤20，0≤k≤50）和所有障礙點的坐標，輸出所有滿足要求的移動序列（用news表示北、東、西、南），按照字典序從小到大排列，最后輸出移動序列的總數(shù)。

【分析】

還是典型的DFS，不過需要注意以下幾點：

（1）因為牽涉較多的坐標處理邏輯，使用二維幾何中的Point類來表示位置以及向量。提前存儲向4個方向走的4個向量，然后再回溯搜索。

（2）停留的點是不能重復的，這個需要在搜索時進行記錄判重，因為最多走20步，所以坐標的最大值可能是20*(20+1)/2=210，使用二維數(shù)組Vis[512][512]進行判重，注意坐標可能為負值，所以在判重之前先加上256：vis[x+256][y+256]。

（3）剪枝優(yōu)化：當前已經(jīng)走了k步，共要走n步，則最多還能走出(n-k) * (k+1+n)/2步，如果當前到(0,0)的距離大于這個數(shù)字，就肯定不能走到終點，直接返回即可。

完整程序（C++11）如下：

習題7-3　多米諾效應(yīng)（The Domino Effect, ACM/ICPC World Finals 1991, UVa211）

一副“雙六”多米諾骨牌包含28張，編號如圖2.35所示。

在7*8網(wǎng)格中每張牌各擺一張，如圖2.36所示，左邊是各個格子的點數(shù)，右邊是各個格子所屬的骨牌編號。

輸入圖2.36所示左圖，你的任務(wù)是輸出所有可能的如圖2.36右圖所示的結(jié)果。

【分析】

使用回溯法，對網(wǎng)格中的坐標從左到右、從上到下進行遍歷，每一步考慮水平和垂直放置兩種方法，如果這個格子已經(jīng)被之前的骨牌占用，則直接遍歷到下一個格子。

注意以下幾點：

（1）對骨牌的面值進行索引，可以根據(jù)牌面的兩個數(shù)值查找對應(yīng)的骨牌編號。

（2）對“按順序跳到下一個Cell”的邏輯進行封裝。

（3）在回溯過程中要記錄已經(jīng)放置過的骨牌編號。

習題7-4　切斷圓環(huán)鏈（Cutting Chains, ACM/ICPC World Finals 2000, UVa818）

有n（n≤15）個圓環(huán)，其中有一些已經(jīng)扣在了一起。現(xiàn)在需要打開盡量少的圓環(huán)，使得所有圓環(huán)可以組成一條鏈（當然，所有打開的圓環(huán)最后都要再次閉合）。例如有5個圓環(huán)，如1-2, 2-3, 4-5，則需要打開一個圓環(huán)，如圓環(huán)4，然后用它穿過圓環(huán)3和圓環(huán)5后再次閉合圓環(huán)4，就可以形成一條鏈：1-2-3-4-5。

【分析】

關(guān)鍵點是把所有圓環(huán)打開之后，肯定能形成一條鏈，所以問題一定有解。因為n≤15，可以用位向量表示并遍歷每個圓環(huán)是否打開，記kc為打開的圓環(huán)的個數(shù)。確定這個集合之后，可把每個未打開的圓環(huán)看作一個結(jié)點，如果兩個圓環(huán)是相連的就在圖中形成一條無向邊，則結(jié)點和邊組成的圖（可能有多個點連通分量）符合以下3個條件即可形成一條鏈。

（1）不能有分叉，也就是說結(jié)點的度數(shù)都小于等于2。

（2）不能有環(huán)，可使用DFS判圈，因為圖為無向圖，所以在DFS到每個點時要傳入父結(jié)點。

（3）每個打開的環(huán)只能連接兩個未打開的環(huán)，也就是兩個連通分量。所以當前連通分量的個數(shù)ti必須滿足ti≤kc+1。ti可以在判圈時一并求出。

本題中使用STL中的bitset來作為位向量。注意在判圈和求度數(shù)時，必須忽略已經(jīng)打開的環(huán)。完整程序如下：

習題7-5　流水線調(diào)度（Pipeline Scheduling, UVa690）

給10個完全相同的任務(wù)安排一個流水線調(diào)度。輸入數(shù)據(jù)是如圖2.37（a）所示的reservation table。在圖2.37中，在時間4時unit0處于工作狀態(tài)。

在你的流水線調(diào)度中不能同時有兩個任務(wù)使用同一個unit。例如若兩個任務(wù)分別在時間0和1開始，則在時間5時unit0會發(fā)生沖突，如圖2.37（b）所示。

輸入一個5行n（n<20）列的resrevation table，輸出10個任務(wù)執(zhí)行完畢所需的最少時間。如上面的例子，答案為34。

【分析】

初步看，就是一個回溯，依次對每個任務(wù)的開始時間進行決策，判斷有無沖突。這樣算法復雜度為10 * 10¹⁰，肯定超時。但是注意本題中的所有任務(wù)都完全相同，在這個前提下，考慮使用以下剪枝：

（1）兩個任務(wù)的開始時間可以有不同的間隔（1～n），但是有的間隔會引起沖突。提前計算出兩個任務(wù)之間所有的合法間隔，進行決策時只是用合法間隔進行下一個任務(wù)的安排。

（2）此類搜索問題中，常見的一個剪枝技巧就是已經(jīng)決策了i個，已用的時間為t，判斷t加上剩下的10-i所需的時間是否已經(jīng)超過當前搜索出的最優(yōu)時間，如果超過，則直接返回。而所有任務(wù)完全相同，因此可以想到將“i個任務(wù)調(diào)度好所需要的最小時間”記錄為A_i。一開始令所有A_i＝i*n，然后從i＝1～10依次求A_i。而求A_i的過程中就可以復用A_10-i來進行上述剪枝。

最終A₁₀就是問題答案。完整程序（C＋＋11）如下：

習題7-6　重疊的正方形（Overlapping Squares, Xi’an 2006, UVa12113）

給出一個4*4的棋盤和棋盤上所呈現(xiàn)出來的紙張邊緣，問用不超過6張2*2的紙能不能擺出這樣的形狀，如圖2.38所示。

【分析】

關(guān)鍵在于棋盤的建模，因為題目需要考慮正方形的邊以及正方形之間的覆蓋。可以將棋盤抽象成一個5*5的Grid，Grid中每個點有兩個狀態(tài)值：從這個點開始向下延伸的邊以及向右延伸的邊分別是否可見。這樣Grid的狀態(tài)個數(shù)就是5*5*2=50個，對應(yīng)的，分別使用兩個32位整數(shù)作為二進制集合即可。

讀取輸入之后建立目標局面target。然后進行回溯，從左到右，從上到下，每次嘗試在所有可能的位置放置一張紙，看看能不能形成目標局面，最多放6張紙。完整程序如下：

習題7-10　守衛(wèi)棋盤（Guarding the Chessboard, UVa11214）

輸入一個n*m棋盤（n,m<10），某些格子有標記。用最少的皇后守衛(wèi)（即占據(jù)或者攻擊）所有帶標記的格子。

【分析】

這個題目也可以像八皇后問題一樣使用回溯法搜索，不過關(guān)鍵也是棋盤的編碼以及決策的順序。

（1）棋盤最大有9*9個格子，也就是用3個32bit的int足以表示每一個格子的狀態(tài)（被覆蓋與否）。本題的時間限制比較緊，狀態(tài)值如果用數(shù)組存儲，狀態(tài)轉(zhuǎn)移以及最終判斷棋盤覆蓋是否為可行解就需要做循環(huán)賦值或者判等操作，會導致TLE。

（2）在決策時，按照從左到右，從上到下的順序依次每個格子進行決策：是否放皇后。

（3）注意每個位置放皇后時因為要設(shè)置一系列的bit值（行列），可以把每個位置放皇后要設(shè)置的所有bit值也預先存到3個int 內(nèi)，然后進行一次“或”的位運算，即可完成狀態(tài)轉(zhuǎn)移。否則還要循環(huán)對每個位賦值，也會導致超時，這也是本題需要使用3個int作為位集合表示棋盤狀態(tài)的最重要原因。

完整程序如下：

習題7-11　樹上的機器人規(guī)劃（簡單版）（Planning mobile robot on Tree (EASY Version), UVa12569）

有一棵n（4≤n≤15）個結(jié)點的樹，其中一個結(jié)點有一個機器人，還有一些結(jié)點有石頭。每步可以把一個機器人或者石頭移到一個相鄰結(jié)點。任何情況下一個結(jié)點里不能有兩個東西（石頭或者機器人）。輸入每個石頭的位置和機器人的起點和終點，求最小步數(shù)的方案。如果有多解，可以輸出任意解。如圖2.39所示，s=1，t=5，最少需要16步：機器人1-6，石頭2-1-7，機器人6-1-2-8，石頭3-2-1-6，石頭4-3-2-1，最后機器人8-2-3-4-5。

【分析】

看到最小步數(shù)問題，首先想到肯定是用BFS。其次是狀態(tài)編碼表示，使用一個int，最低4位就可以表示機器人的位置。然后剩下的位表示每個結(jié)點上是否有石頭，這樣就可以用一個int數(shù)組來進行狀態(tài)判重。可將設(shè)置狀態(tài)各個部分的位運算代碼封裝起來。每次考慮是機器人移動還是石頭移動，嘗試往各個方向移動，生成新的狀態(tài)進行搜索即可。

習題7-12　移動小球（Moving Pegs, ACM/ICPC Taejon 2000,UVa1533）

如圖2.40所示，一共有15個洞，其中一個空著，剩下的洞里各有一個小球。每次可以讓一個小球越過同一條直線上的一個或多個小球后跳到最近的空洞中，然后拿走被跳過的小球。如讓14跳到空洞5中，則洞9里的小球會被拿走，因此操作之后洞9和14會變空，而5里面會有一個小球。你的任務(wù)是用最少的步數(shù)讓整個棋盤只剩下一個小球，并且這個小球留在最初輸入的空洞中。

輸入僅包含一個整數(shù)，即空洞編號，輸出最短序列的長度m，然后是m個整數(shù)對，分別表示每次跳躍的小球所在的洞編號以及目標洞的編號。

【分析】

棋盤上小球的跳躍規(guī)則比較散亂，可以對每個洞一步就跳到下一個空洞的路徑進行編號，按照從小到大的順序排成一個表格：左上，右上，左，右，左下，右下，如果跳出邊界就用0來表示。

可以使用一個位向量來表示當前棋盤的局面。同時要記錄從初始狀態(tài)到當前狀態(tài)的跳躍路徑（每一次跳躍都記錄起點和目的點）。

最后就是使用BFS來對所有的狀態(tài)進行搜索，每一步可以選擇一個球的位置（按照從小到大的順序來選），然后同樣按照從小到大的順序嘗試往6個方向跳到最近的空洞。所有合法的跳轉(zhuǎn)都將產(chǎn)生一個新的狀態(tài)，同時還要使用一個set<int>對所有已經(jīng)入隊的棋盤局面（前述的二進制表示）進行判重，每一個新局面如果已經(jīng)入隊，就退出。

程序代碼（C++11）如下：

習題7-15　最大的數(shù)（Biggest Number, UVa11882）

在一個R行C列（2≤R, C≤15，R*C≤30）的矩陣里有障礙物和數(shù)字格（包含1～9的數(shù)字）。你可以從任意一個數(shù)字格出發(fā)，每次沿著上下左右之一的方向走一格，但不能走到障礙格中，也不能重復經(jīng)過一個數(shù)字格，然后把沿途經(jīng)過的所有數(shù)字連起來。

如圖2.41所示，你可以得到9784、4832145等整數(shù)。問：能得到的最大整數(shù)是多少？

【分析】

直接暴力搜索，就是考慮當前的位置、走過的位置，以及已經(jīng)走出來的整數(shù)作為當前狀態(tài)，每次走一步，看看后續(xù)能走出多大的整數(shù)。但是這樣極端情況下狀態(tài)個數(shù)約為430，肯定會超時。

可以考慮兩個剪枝優(yōu)化：

（1）走到一個點（x,y），當前已經(jīng)走出的數(shù)字序列是cur，已經(jīng)搜到的最優(yōu)答案為ans。往下搜索之前，看看最多還能走出幾步。可以使用BFS把跟當前點依然連通的數(shù)字搜索出來（不包括已經(jīng)走過的），記這個數(shù)字序列為rs，那么這個rs的長度就是后續(xù)能走出的步數(shù)上限，如果cur.size()+rs.size() < ans.size()，說明無論如何走出來的數(shù)字長度都不會超過ans。也就不可能搜出最優(yōu)解，直接退出。

（2）如果cur.size()+rs.size()==ans.size()，說明有可能走出更大的數(shù)字，那就把rs從大到小排序，如果排序后的cur和rs拼起來小于ans對應(yīng)的數(shù)字，直接退出。

完整程序如下：

習題7-18　推門游戲（The Wall Pusher, UVa10384）

如圖2.42所示，你從S處出發(fā)，每次可以往東、南、西、北4個方向之一前進。如果前方有墻壁，游戲者可以把墻壁往前推一格。如果有兩堵或者多堵連續(xù)的墻，游戲者不能將它們推動。另外，游戲者也不能把游戲區(qū)域邊界上的墻推動。

用最少的步數(shù)走出迷宮（邊界處沒有墻的地方就是出口）。迷宮總是有4行6列，多解時任意輸出一個移動序列即可（用NEWS4個字符表示移動方向）。

【分析】

如果使用BFS，搜索時除了當前的位置，還要考慮墻的狀態(tài)，結(jié)點判重更不好處理。所以考慮使用迭代加深搜索（IDFS）作為主算法框架。

每步有兩種可能的走法：

（1）沿著這個方向可以直接走到下一個格子。

（2）可以沿著當前的方向把墻推到下一個格子。

然后就可以從當前位置每一步選擇4個方向其中之一搜索即可。程序?qū)崿F(xiàn)上有以下幾點需要注意：

（1）使用0、1、2、3來表示W(wǎng)NES這4個方向，然后輸出時再轉(zhuǎn)換即可。

（2）使用兩個數(shù)組來存儲4個方向的向量：int DX[]={ 0,-1, 0, 1 }，DY[]={-1, 0, 1, 0 }。

（3）使用一個數(shù)組來表示4個方向的反方向：REVD[]={ 2, 3, 0, 1 }，用來在推門時給下一個格子去掉對應(yīng)的墻，詳細參見代碼。這樣遍歷4個方向的代碼就可以統(tǒng)一處理。

完整程序（C++11）如下：