算法分析与设计：习题选讲第五章

1、习题选讲2011-12-222第五章1317 Sudoku1215 脱离地牢1050 Numbers & Letters1171 The Game of Efil1219 新红黑树1048 Inverso1135 飞越原野1107 Simple Puzzle2011-12-2231317 Sudoku题目大意：给出一个未完成的数独，问这个数独有多少个解。2011-12-2241317 Sudoku解题思路：规则就是用19的数字把空格填满，使得9行，9列以及9个小的33方格内都有19这9个数字。 使用深度优先搜索+剪枝。2011-12-2251317 Sudoku暴力搜索：按照格子顺序，枚举每个

2、格子可能出现的数字，如果发现矛盾则回溯。直到找出所有解。绝对会超时。2011-12-2262011-12-2271317 Sudoku剪枝：使用数独技巧。搜索时，对每个格子，根据同行同列和同小方格已有的数字，判断当前格子可能填上的数字，如果只有一个数字可填，则可以马上填上。仍然会超时。2011-12-2281317 Sudoku另一个剪枝：如果有个数字在某一行某一列某个小方格里面只找到1个位置，则可以马上填上。加上这个剪枝即可通过。8/viewsource.php?sid=806782011-12-2291215 脱离地牢题目大意：有两个人在一个地牢里，里面有墙壁也有熔浆。当一个人向某个方向移

3、动时，另一个人会向另一个方向移动。如果遇到墙壁则不能前进，如到熔浆则任务失败。问使两个人相遇最少需要多少步。2011-12-22101215 脱离地牢解题思路：从初始状态开始进行bfs，状态为两个人分别的位置。一个状态，可以通过一个人向东南西北四个方向移动，同时另外一个人也跟着移动，到达新状态。重复状态不加入队列。直到两个人相遇。8/viewsource.php?sid=870552011-12-22111171 The Game of Efil题目大意：一块m*n大小的板上，有一些细菌。如果一个细菌的八个方向上邻居细菌数是2或3，则在下一个回合它能保留下来，否则它会消失。如果有一个空格的邻居

4、细菌数为3，则下一回合长出新的细菌。板的上下边是连通的，左右边是连通的。给出一个板的当前状态，问上一个回合的状态有多少不同的情况。m*n=162011-12-22121171 The Game of Efil解题思路：枚举出每种状态，按照规则生成下一步状态，并与输入状态比较，相等则答案数加一。因为最多有16个格子，因此最多有216个状态。枚举状态用dfs。2011-12-22131171 The Game of Efilvoid dfs(int x,int y) if (x=m) cal();return;dxy=0;if (y=n-1) dfs(x+1,0);else dfs(x,y+1);

5、dxy=1;if (y=n-1) dfs(x+1,0);else dfs(x,y+1);2011-12-22141171 The Game of Efilvoid cal() int i,j,k,temp,t; for (i=0;im;i+) for (j=0;jn;j+) temp=0; for (k=0;k8;k+) if (d(i+dxk+m)%m(j+dyk+n)%n) temp+; if (temp=3) t=1; else if (dij=1&temp=2) t=1; else t=0; if (strdij!=t) return; ans+; return;2011-12-221

6、51219 新红黑树题目大意：一棵树由红枝和黑枝组成的树，A和B轮流砍树，A只砍红枝，B只砍黑枝。砍枝后不与根相连的枝都去掉。每个树枝上有权值，砍掉的枝的权值加到自己的分数上。A想使A-B之差越高越好，B想它越低越好。在最佳策略下A-B之差。树枝树不超过20。2011-12-22161219 新红黑树解题思路：这题是博弈题，可以看作在博弈树上进行深搜，并根据两人的策略取最大值或最小值。博弈状态有重复，状态只包括，当前剩下的树枝，和轮到谁砍树枝。使用记忆化搜索。预处理砍掉每个树枝会使哪些其它树枝消失。预处理使用dfs。位操作。2011-12-22171219 新红黑树int dfs(int k)

7、 int i,temp=0;visk=1;for (i=0;in;i+) if (bi=k)swap(ai,bi);if (ai=k&visbi=0) cuti=(dfs(bi)|(1i);temp|=cuti;return temp;2011-12-22181219 新红黑树int cal(int z,int t) int i,tt,temp;if (z=0) return 0;tt=(t+1)/2;if (dttz) return recttz;for (i=0;in;i+) if (ci=t&(z&(1recttz*t) dttz=1;recttz=temp;if (!dttz) dtt

8、z=1; recttz=cal(z,-t); return recttz;2011-12-22191048 Inverso题目大意：给出一个3*3棋盘，每个格子是黑色或白色。每个格子有一个按钮，按这个按钮会使自己和周围8个方向的格子颜色反转。问最少需要多少步使所有格子变成白色，输出最小的序列。2011-12-22201048 Inverso解题思路：任何一个按钮按两次以上都是没用的，因为按两次的作用互相抵消了。枚举每个格子按或者不按，判断是否能使所有格子变成白色，如果可以，则取所有方案的最小值。需要特判，初始时全部格子为白色。2011-12-22211048 Inversovoid dfs(i

9、nt grid,int cnt) if (grid9) tempanscnt=0;if (allwhite()&better(tempans,ans)strcpy(ans,tempans);return;dfs(grid+1,cnt);flip(grid);tempanscnt=grid+0;dfs(grid+1,cnt+1);return;2011-12-22221135 飞越原野题目大意：在m*n的平面上，有一个德鲁伊，可以用1的时间向四个方向走一步，或用1的时间向四个方向飞任意距离。飞行降落点和行走必须在平地上。飞行的总距离有限制。问从(1,1)飞到(m,n)的最短时间。2011-12-

10、22231135 飞越原野解题思路：进行bfs。状态为当前所在格子坐标(x,y)，当前可用飞行距离d，初始状态为(0,0,d)，终止状态为(m,n,x)，其中x可以为任意非负整数。每个状态，可以向四个方向走一步，或向四个方向飞任意距离，都消耗时间1。2011-12-22241135 飞越原野struct state int x,y,d,s;queue q;int dx4=0,1,0,-1,dy4=1,0,-1,0;2011-12-22251135 飞越原野int bfs() state temp1,temp2; q.push(state(1,1,D,0); while (!q.empty()

11、temp1=q.top(); q.pop(); if (temp1.x=m&temp2.y=n) return temp1.s; for (int k=0;k4;k+) temp2=walk(temp1,k); if (valid(temp2) q.push(temp2); for (int i=1;i=temp1.d,i+) temp2=fly(temp1,k,i); if (vaild(temp2) q.push(temp2); 2011-12-22261135 飞越原野state walk(state temp,int k) temp.x+=dxk;temp.y+=dyk;temp.s+

12、;return temp;state fly(state temp,int k,int step) temp.x+=dxk*step;temp.y+=dyk*step;temp.d-=step;temp.s+;return temp;2011-12-22271135 飞越原野bool valid(state temp) if (temp.xm|temp.yn)return false;if (graphtemp.xtemp.y=L)return false;if (hashtemp.xtemp.ytemp.d)return false;hashtemp.xtemp.ytemp.d=true;r

13、eturn true;2011-12-22281107 Simple Puzzle题目大意：给出n个数，每个数有k个数字，现在把这n个数写成n行，并且对齐成k列，在每个数中擦去一个数字，并且擦去的数字的列要不相同，得到n个不完整的数。现在给出这n个不完整的数和初始n个数的和，求这个n个数。2011-12-22291107 Simple Puzzle解题思路：枚举n个数中每个数缺失的位，并且缺失的位应该填上的数字，然后检查所有数的和是否和输入相等，相等则记下。枚举用dfs。对所有答案排序输出。2011-12-22301107 Simple Puzzleint dfs(int m) if (m=n) check();return;int temp=am;for (int i=0;ik;i+) if (di) continue;di=true;for (int j=0;j=9;j+) am=add_digit(temp,i,j);dfs(m+1);di=false;am=temp;2011-12-22311107 Simple Puzzleint add_digit(int x,