c++深度优先搜索(dfs)习题.doc

《c++深度优先搜索(dfs)习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、红与黑题目描述有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。输入开头行包含两个正整数W和H，W和H分别表示矩形房间的列数和行数，且都不超过20.每个数据集有H行，其中每行包含W个字符。每个字符的含义如下所示：'.'——黑砖'#'——红砖'@'——男子（仅出现一次）输出程序应该输出一行，包含男子从初始瓷砖出发可到达的瓷砖数样例输入69....#......#.

2、.............................#@...#.#..#.样例输出45迷宫问题题目描述设有一个N*N(2<=N<=10)方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通，1表示不能，入口和出口处肯定是0.迷宫走的规则如下所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可通过，要另找路径。找出所有从入口（左上角）到出口（右上角）的路径（不能重复），输出路径总数，如果无法到达，则输出0.输入第一行输入N,接下来输入N*N的矩阵输出输出路径总数

3、样例输入3000011100样例输出2单词接龙题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。输入输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开

4、头的字母。你可以假定以此字母开头的“龙”一定存在.输出只需输出以此字母开头的最长的“龙”的长度样例输入5attouchcheatchoosetacta样例输出23选数题目描述　　已知n个整数x1,x2,…,xn，以及一个整数k（k＜n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k＝3，4个整数分别为3，7，12，19时，可得全部的组合与它们的和为：3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为

5、素数：3＋7＋19＝29）。输入键盘输入，格式为：n,k（1<=n<=20，k＜n）x1,x2，…,xn（1<=xi<=）输出　屏幕输出，格式为：一个整数（满足条件的种数）。样例输入43371219样例输出1N皇后题目描述检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。 列号->1234561O2O3O4O5O6O上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下： 行号 1 2

6、 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。 特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。输入一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。 输出前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。 样例输入6样例输出24

7、61353625144152634马的遍历题目描述在n*m(n表示行，m表示列）的棋盘上，马起始位置为x,y（注意：左上角第一个位置为1,1），问：马有多少种走的方法，将棋盘所有的位置全部走一遍，并且每个位置经过且仅经过一次。输入第一行：n，m（中间空格隔开）（n,m<7）第二行：x，y（中间空格隔开）输出可能的方法数样例输入5411样例输出32