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

  2018-12-17来源:网络

  原标题:c++深度优先搜索(dfs)习题

红与黑
题目描述有一个矩形房间,覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上,由此出发,可以移到四个相邻瓷砖之一,但他不能移动到红砖上,只能移动到黑砖上。编写一个程序,计算他通过重复上述移动所能经过的黑砖数。输入开头行包含两个正整数W和H,W和H分别表示矩形房间的列数和行数,且都不超过20.每个数据集有H行,其中每行包含W个字符。每个字符的含义如下所示:.——黑砖#——红砖@——男子(仅出现一次)输出程序应该输出一行,包含男子从初始瓷砖出发可到达的瓷砖数样例输入69....#......#..............................#@...#.#..#.
样例输出45
迷宫问题
题目描述设有一个N*N(2=N=10)方格的迷宫,入口和出口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通,1表示不能,入口和出口处肯定是0.迷宫走的规则如下所示:即从某点开始,有八个方向可走,前进方格中数字为0时表示可通过,为1时表示不可通过,要另找路径。找出所有从入口(左上角)到出口(右上角)的路径(不能重复),输出路径总数,如果无法到达,则输出0.输入第一行输入N,接下来输入N*N的矩阵输出输出路径总数样例输入3000011100
样例输出
2
单词接龙
题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at和atide间不能相连。输入输入的第一行为一个单独的整数n(n=20)表示单词数,以下n行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出只需输出以此字母开头的最长的“龙”的长度样例输入5attouchcheatchoosetacta
样例输出23
选数
题目描述已知n个整数x1,x2,?,xn,以及一个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。例如当n=4,k=3,4个整数分别为3,7,12,19时,可得全部的组合与它们的和为:3+7+12=223+7+19=297+12+19=383+12+19=34。现在,要求你计算出和为素数共有多少种。例如上例,只有一种的和为素数:3+7+19=29)。输入键盘输入,格式为:n,k(1=n=20,k<n)x1,x2,?,xn(1=xi=5000000)输出屏幕输出,格式为:一个整数(满足条件的种数)。样例输入
43371219
样例输出
1
N皇后
题目描述检查一个如下的6x6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。列号-123456OOO123456OOO
上面的布局可以用序列246135来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:行号123456列号246135这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。特别注意:对于更大的N(棋盘大小NxN)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式),这是作弊。输入一个数字N输出前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。(6=N=13)表示棋盘是NxN大小的。
样例输入
6
样例输出
2461353625144152634
马的遍历
题目描述在n*m(n表示行,m表示列)的棋盘上,马起始位置为x,y(注意:左上角第一个位置为1,1),问:马有多少种走的方法,将棋盘所有的位置全部走一遍,并且每个位置经过且仅经过一次。输入第一行:n,m(中间空格隔开)(n,m7)第二行:x,y(中间空格隔开)输出可能的方法数样例输入
5411
样例输出
32