《算法分析习题课 第五章》由会员分享，可在线阅读，更多相关《算法分析习题课 第五章（29页珍藏版）》请在金锄头文库上搜索。
1、算法分析习题选讲(第五章)第五章1317 Sudoku1215 脱离地牢1050 Numbers & Letters1171 The Game of Efil1219 新红黑树1048 Inverso1135 飞越原野1107 Simple Puzzle1317 Sudoku题目大意：给出一个未完成的数独，问这个数独有多少个解。解题思路规则就是用19的数字把空格填满使得9行，9列以及9个小的33方格内都有19这9个数字。 使用深度优先搜索+剪枝dancing links暴力搜索按照格子顺序枚举每个格子可能出现的数字如果发现矛盾则回溯直到找出所有解绝对会超时剪枝使用数独技巧。搜索时，对每个格子，
2、根据同行同列和同小方格已有的数字，判断当前格子可能填上的数字，如果只有一个数字可填，则可以马上填上。仍然会超时。另一个剪枝如果有个数字在某一行某一列某个小方格里面只找到1个位置，则可以马上填上。加上这个剪枝即可通过。http:/ 脱离地牢有两个人在一个地牢里，里面有墙壁也有熔浆。当一个人向某个方向移动时，另一个人会向另一个方向移动。如果遇到墙壁则不能前进，如到熔浆则任务失败。问使两个人相遇最少需要多少步。解题思路从初始状态开始进行bfs，状态为两个人分别的位置。一个状态，可以通过一个人向东南西北四个方向移动，同时另外一个人也跟着移动，到达新状态。重复状态不加入队列。直到两个人相遇。 The G
3、ame of Efil一块m*n大小的板上，有一些细菌。如果一个细菌的八个方向上邻居细菌数是2或3，则在下一个回合它能保留下来，否则它会消失。如果有一个空格的邻居细菌数为3，则下一回合长出新的细菌。板的上下边是连通的，左右边是连通的。给出一个板的当前状态，问上一个回合的状态有多少不同的情况。m*n=16解题思路枚举出每种状态，按照规则生成下一步状态，并与输入状态比较，相等则答案数加一。因为最多有16个格子，因此最多有216个状态。枚举状态用dfs。void dfs(int x,int y) if (x=m) cal();return;dxy=0;if (y=n-1) dfs(x+1,0);el
4、se dfs(x,y+1);dxy=1;if (y=n-1) dfs(x+1,0);else dfs(x,y+1);void cal() int i,j,k,temp,t; for (i=0;im;i+) for (j=0;jn;j+) temp=0; for (k=0;k9) 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;1135 飞越原野在m*n的平面
5、上，有一个德鲁伊，可以用1的时间向四个方向走一步，或用1的时间向四个方向飞任意距离。飞行降落点和行走必须在平地上。飞行的总距离有限制。问从(1,1)飞到(m,n)的最短时间。解题思路进行bfs。状态为当前所在格子坐标(x,y)，当前可用飞行距离d，初始状态为(0,0,d)，终止状态为(m,n,x)，其中x可以为任意非负整数。每个状态，可以向四个方向走一步，或向四个方向飞任意距离，都消耗时间1。1107 Simple Puzzle给出n个数，每个数有k个数字，现在把这n个数写成n行，并且对齐成k列，在每个数中擦去一个数字，并且擦去的数字的列要不相同，得到n个不完整的数。现在给出这n个不完整的数和初始n个数的和，求这个n个数。解题思路枚举n个数中每个数缺失的位，并且缺失的位应该填上的数字，然后检查所有数的和是否和输入相等，相等则记下。枚举用dfs。对所有答案排序输出。
