2.5 暴力求解法
本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第7章。
习题7-1 消防车（Firetruck, ACM/ICPC World Finals 1991, UVa208）
输入一个n（n≤20）个结点的无向图以及某个结点k，按照字典序从小到大顺序输出从结点1到结点k的所有路径，要求结点不能重复经过。
提示：
要实现判断结点1是否可以到达结点k，否则会超时。
【分析】
如果1和k不连通，直接DFS搜索路径的话，一定会超时。而要判断1和k是否连通，使用《算法竞赛入门经典（第2版）》第11.2.1节中介绍的并查集即可。
本题建图时每个结点的邻居可以使用set<int>存储，这样输入之后自然就是排好序的。使用DFS从1开始搜索到k的所有路径。因为结点不能重复经过，所以要在搜索过程中对已经经过的结点进行判重。完整程序（C++11）如下：
习题7-2 黄金图形（Golygons, ACM/ICPC World Finals 1993, UVa225）
图2.34
平面上有k个障碍点。从(0,0)点出发，第一次走1个单位，第二次走2个单位，……，第n次走n个单位，恰好回到(0,0)。要求只能沿着东南西北方向走，且每次必须转弯90°（不能沿着同一个方向继续走，也不能后退）。走出的图形可以自交，但不能经过障碍点，如图2.34所示。
输入n、k（1≤n≤20，0≤k≤50）和所有障碍点的坐标，输出所有满足要求的移动序列（用news表示北、东、西、南），按照字典序从小到大排列，最后输出移动序列的总数。
【分析】
还是典型的DFS，不过需要注意以下几点：
（1）因为牵涉较多的坐标处理逻辑，使用二维几何中的Point类来表示位置以及向量。提前存储向4个方向走的4个向量，然后再回溯搜索。
（2）停留的点是不能重复的，这个需要在搜索时进行记录判重，因为最多走20步，所以坐标的最大值可能是20*(20+1)/2=210，使用二维数组Vis[512][512]进行判重，注意坐标可能为负值，所以在判重之前先加上256：vis[x+256][y+256]。
（3）剪枝优化：当前已经走了k步，共要走n步，则最多还能走出(n-k) * (k+1+n)/2步，如果当前到(0,0)的距离大于这个数字，就肯定不能走到终点，直接返回即可。
完整程序（C++11）如下：
习题7-3 多米诺效应（The Domino Effect, ACM/ICPC World Finals 1991, UVa211）
一副“双六”多米诺骨牌包含28张，编号如图2.35所示。
图2.35
在7*8网格中每张牌各摆一张，如图2.36所示，左边是各个格子的点数，右边是各个格子所属的骨牌编号。
图2.36
输入图2.36所示左图，你的任务是输出所有可能的如图2.36右图所示的结果。
【分析】
使用回溯法，对网格中的坐标从左到右、从上到下进行遍历，每一步考虑水平和垂直放置两种方法，如果这个格子已经被之前的骨牌占用，则直接遍历到下一个格子。
注意以下几点：
（1）对骨牌的面值进行索引，可以根据牌面的两个数值查找对应的骨牌编号。
（2）对“按顺序跳到下一个Cell”的逻辑进行封装。
（3）在回溯过程中要记录已经放置过的骨牌编号。
习题7-4 切断圆环链（Cutting Chains, ACM/ICPC World Finals 2000, UVa818）
有n（n≤15）个圆环，其中有一些已经扣在了一起。现在需要打开尽量少的圆环，使得所有圆环可以组成一条链（当然，所有打开的圆环最后都要再次闭合）。例如有5个圆环，如1-2, 2-3, 4-5，则需要打开一个圆环，如圆环4，然后用它穿过圆环3和圆环5后再次闭合圆环4，就可以形成一条链：1-2-3-4-5。
【分析】
关键点是把所有圆环打开之后，肯定能形成一条链，所以问题一定有解。因为n≤15，可以用位向量表示并遍历每个圆环是否打开，记kc为打开的圆环的个数。确定这个集合之后，可把每个未打开的圆环看作一个结点，如果两个圆环是相连的就在图中形成一条无向边，则结点和边组成的图（可能有多个点连通分量）符合以下3个条件即可形成一条链。
（1）不能有分叉，也就是说结点的度数都小于等于2。
（2）不能有环，可使用DFS判圈，因为图为无向图，所以在DFS到每个点时要传入父结点。
（3）每个打开的环只能连接两个未打开的环，也就是两个连通分量。所以当前连通分量的个数ti必须满足ti≤kc+1。ti可以在判圈时一并求出。
本题中使用STL中的bitset来作为位向量。注意在判圈和求度数时，必须忽略已经打开的环。完整程序如下：
习题7-5 流水线调度（Pipeline Scheduling, UVa690）
给10个完全相同的任务安排一个流水线调度。输入数据是如图2.37（a）所示的reservation table。在图2.37中，在时间4时unit0处于工作状态。
在你的流水线调度中不能同时有两个任务使用同一个unit。例如若两个任务分别在时间0和1开始，则在时间5时unit0会发生冲突，如图2.37（b）所示。
图2.37
输入一个5行n（n<20）列的resrevation table，输出10个任务执行完毕所需的最少时间。如上面的例子，答案为34。
【分析】
初步看，就是一个回溯，依次对每个任务的开始时间进行决策，判断有无冲突。这样算法复杂度为10 * 1010，肯定超时。但是注意本题中的所有任务都完全相同，在这个前提下，考虑使用以下剪枝：
（1）两个任务的开始时间可以有不同的间隔（1～n），但是有的间隔会引起冲突。提前计算出两个任务之间所有的合法间隔，进行决策时只是用合法间隔进行下一个任务的安排。
（2）此类搜索问题中，常见的一个剪枝技巧就是已经决策了i个，已用的时间为t，判断t加上剩下的10-i所需的时间是否已经超过当前搜索出的最优时间，如果超过，则直接返回。而所有任务完全相同，因此可以想到将“i个任务调度好所需要的最小时间”记录为Ai。一开始令所有Ai＝i*n，然后从i＝1～10依次求Ai。而求Ai的过程中就可以复用A10-i来进行上述剪枝。
最终A10就是问题答案。完整程序（C＋＋11）如下：
习题7-6 重叠的正方形（Overlapping Squares, Xi’an 2006, UVa12113）
给出一个4*4的棋盘和棋盘上所呈现出来的纸张边缘，问用不超过6张2*2的纸能不能摆出这样的形状，如图2.38所示。
图2.38
【分析】
关键在于棋盘的建模，因为题目需要考虑正方形的边以及正方形之间的覆盖。可以将棋盘抽象成一个5*5的Grid，Grid中每个点有两个状态值：从这个点开始向下延伸的边以及向右延伸的边分别是否可见。这样Grid的状态个数就是5*5*2=50个，对应的，分别使用两个32位整数作为二进制集合即可。
读取输入之后建立目标局面target。然后进行回溯，从左到右，从上到下，每次尝试在所有可能的位置放置一张纸，看看能不能形成目标局面，最多放6张纸。完整程序如下：
习题7-10 守卫棋盘（Guarding the Chessboard, UVa11214）
输入一个n*m棋盘（n,m<10），某些格子有标记。用最少的皇后守卫（即占据或者攻击）所有带标记的格子。
【分析】
这个题目也可以像八皇后问题一样使用回溯法搜索，不过关键也是棋盘的编码以及决策的顺序。
（1）棋盘最大有9*9个格子，也就是用3个32bit的int足以表示每一个格子的状态（被覆盖与否）。本题的时间限制比较紧，状态值如果用数组存储，状态转移以及最终判断棋盘覆盖是否为可行解就需要做循环赋值或者判等操作，会导致TLE。
（2）在决策时，按照从左到右，从上到下的顺序依次每个格子进行决策：是否放皇后。
（3）注意每个位置放皇后时因为要设置一系列的bit值（行列），可以把每个位置放皇后要设置的所有bit值也预先存到3个int 内，然后进行一次“或”的位运算，即可完成状态转移。否则还要循环对每个位赋值，也会导致超时，这也是本题需要使用3个int作为位集合表示棋盘状态的最重要原因。
完整程序如下：
习题7-11 树上的机器人规划（简单版）（Planning mobile robot on Tree (EASY Version), UVa12569）
有一棵n（4≤n≤15）个结点的树，其中一个结点有一个机器人，还有一些结点有石头。每步可以把一个机器人或者石头移到一个相邻结点。任何情况下一个结点里不能有两个东西（石头或者机器人）。输入每个石头的位置和机器人的起点和终点，求最小步数的方案。如果有多解，可以输出任意解。如图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。
【分析】
图2.39
看到最小步数问题，首先想到肯定是用BFS。其次是状态编码表示，使用一个int，最低4位就可以表示机器人的位置。然后剩下的位表示每个结点上是否有石头，这样就可以用一个int数组来进行状态判重。可将设置状态各个部分的位运算代码封装起来。每次考虑是机器人移动还是石头移动，尝试往各个方向移动，生成新的状态进行搜索即可。
习题7-12 移动小球（Moving Pegs, ACM/ICPC Taejon 2000,UVa1533）
如图2.40所示，一共有15个洞，其中一个空着，剩下的洞里各有一个小球。每次可以让一个小球越过同一条直线上的一个或多个小球后跳到最近的空洞中，然后拿走被跳过的小球。如让14跳到空洞5中，则洞9里的小球会被拿走，因此操作之后洞9和14会变空，而5里面会有一个小球。你的任务是用最少的步数让整个棋盘只剩下一个小球，并且这个小球留在最初输入的空洞中。
图2.40
输入仅包含一个整数，即空洞编号，输出最短序列的长度m，然后是m个整数对，分别表示每次跳跃的小球所在的洞编号以及目标洞的编号。
【分析】
棋盘上小球的跳跃规则比较散乱，可以对每个洞一步就跳到下一个空洞的路径进行编号，按照从小到大的顺序排成一个表格：左上，右上，左，右，左下，右下，如果跳出边界就用0来表示。
可以使用一个位向量来表示当前棋盘的局面。同时要记录从初始状态到当前状态的跳跃路径（每一次跳跃都记录起点和目的点）。
最后就是使用BFS来对所有的状态进行搜索，每一步可以选择一个球的位置（按照从小到大的顺序来选），然后同样按照从小到大的顺序尝试往6个方向跳到最近的空洞。所有合法的跳转都将产生一个新的状态，同时还要使用一个set<int>对所有已经入队的棋盘局面（前述的二进制表示）进行判重，每一个新局面如果已经入队，就退出。
程序代码（C++11）如下：
习题7-15 最大的数（Biggest Number, UVa11882）
在一个R行C列（2≤R, C≤15，R*C≤30）的矩阵里有障碍物和数字格（包含1～9的数字）。你可以从任意一个数字格出发，每次沿着上下左右之一的方向走一格，但不能走到障碍格中，也不能重复经过一个数字格，然后把沿途经过的所有数字连起来。
如图2.41所示，你可以得到9784、4832145等整数。问：能得到的最大整数是多少？
图2.41
【分析】
直接暴力搜索，就是考虑当前的位置、走过的位置，以及已经走出来的整数作为当前状态，每次走一步，看看后续能走出多大的整数。但是这样极端情况下状态个数约为430，肯定会超时。
可以考虑两个剪枝优化：
（1）走到一个点（x,y），当前已经走出的数字序列是cur，已经搜到的最优答案为ans。往下搜索之前，看看最多还能走出几步。可以使用BFS把跟当前点依然连通的数字搜索出来（不包括已经走过的），记这个数字序列为rs，那么这个rs的长度就是后续能走出的步数上限，如果cur.size()+rs.size() < ans.size()，说明无论如何走出来的数字长度都不会超过ans。也就不可能搜出最优解，直接退出。
（2）如果cur.size()+rs.size()==ans.size()，说明有可能走出更大的数字，那就把rs从大到小排序，如果排序后的cur和rs拼起来小于ans对应的数字，直接退出。
注意：
对应的数字可能超过30位，可以用一个vector<char>来储存，这样数字的修改和数字之间的比较都比较方便。
完整程序如下：
习题7-18 推门游戏（The Wall Pusher, UVa10384）
如图2.42所示，你从S处出发，每次可以往东、南、西、北4个方向之一前进。如果前方有墙壁，游戏者可以把墙壁往前推一格。如果有两堵或者多堵连续的墙，游戏者不能将它们推动。另外，游戏者也不能把游戏区域边界上的墙推动。
图2.42
用最少的步数走出迷宫（边界处没有墙的地方就是出口）。迷宫总是有4行6列，多解时任意输出一个移动序列即可（用NEWS4个字符表示移动方向）。
【分析】
如果使用BFS，搜索时除了当前的位置，还要考虑墙的状态，结点判重更不好处理。所以考虑使用迭代加深搜索（IDFS）作为主算法框架。
每步有两种可能的走法：
（1）沿着这个方向可以直接走到下一个格子。
（2）可以沿着当前的方向把墙推到下一个格子。
然后就可以从当前位置每一步选择4个方向其中之一搜索即可。程序实现上有以下几点需要注意：
（1）使用0、1、2、3来表示WNES这4个方向，然后输出时再转换即可。
（2）使用两个数组来存储4个方向的向量：int DX[]={ 0,-1, 0, 1 }，DY[]={-1, 0, 1, 0 }。
（3）使用一个数组来表示4个方向的反方向：REVD[]={ 2, 3, 0, 1 }，用来在推门时给下一个格子去掉对应的墙，详细参见代码。这样遍历4个方向的代码就可以统一处理。
完整程序（C++11）如下：
