【原创】dfs

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 0

1 1 1 1 0

0 1 1 1 0

1 0 0 1 1

1 0 1 0 1

样例输出：

yes

（阅读量破10公布正确代码。）