dfs是一种搜索。例如,现在我们有一个数字三角形,需要计算从最上面的顶点开始到最下面一行的最大权值和。只可以往下或者右下走。 1 2 3 1 6 10 我们需要不断枚举。我们发现,枚举动作是递归进行的。每一次,把枚举后的和加上去,然后分下,右两种情况分类枚举。直到最后一行位置。因此,我们可以写一个递归函数。 ans指当前权值和。x指行,y指列。这种递归的写法就叫做dfs,深度优先搜索。对于二叉树的两个分支,我们分两种情况向下搜索。这就是dfs的原理。 思考题:走迷宫。现在有一个长m宽n的迷宫,1表示可以走,0表示不能走。用dfs的方法,判断从左上到右下是否有路。 输入:第一行m,n,后面是由0和1构成的数组。 输出:yes表示有路,no表示没有路。 样例输入: 5 5 1 0 1 0 01 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 样例输出: yes (阅读量破10公布正确代码。)
|
|