c++DFS算法问题?

Question

c++DFS算法问题

Answer 1

这个题是比较基本的DFS问题，建议你自己多看多试一下，自己做出来意义更大一点。我想提供给你另外一种思路，时间复杂度更低，对于每个坐标（X，Y）可以从（x-1，y）和（x，y-1）到达，所以到这一点的可能数就是到达两个先驱点的方案数量的和，把黑洞设置成0就行了

Answer 2

1234567891011121314151617181920212223242526272829303132#include&nbsp;"iostream"#include&nbsp;<string.h>using&nbsp;namespace&nbsp;std;int&nbsp;c&nbsp;=&nbsp;0;int&nbsp;n,&nbsp;m,&nbsp;num;int&nbsp;arr[20][20];void&nbsp;search(int&nbsp;x,&nbsp;int&nbsp;y){&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(x&nbsp;>&nbsp;n&nbsp;||&nbsp;y&nbsp;<&nbsp;1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;&nbsp;&nbsp;&nbsp;&nbsp;if(arr[x][y]&nbsp;==&nbsp;1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//碰到黑洞&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(x&nbsp;==&nbsp;n&nbsp;&&&nbsp;y&nbsp;==&nbsp;1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c++;&nbsp;&nbsp;&nbsp;&nbsp;search(x&nbsp;+&nbsp;1,&nbsp;y);&nbsp;&nbsp;&nbsp;&nbsp;search(x,&nbsp;y&nbsp;-&nbsp;1);&nbsp;&nbsp;&nbsp;&nbsp;return;}int&nbsp;main(){&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;x,&nbsp;y;&nbsp;&nbsp;&nbsp;&nbsp;memset(arr,&nbsp;0,sizeof&nbsp;arr);&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;>>&nbsp;n&nbsp;>>&nbsp;m&nbsp;>>&nbsp;num;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;num;&nbsp;i++)&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;>>&nbsp;x&nbsp;>>&nbsp;y;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr[x][y]&nbsp;=&nbsp;1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//1代表黑洞&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;search(1,&nbsp;m);&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;<<&nbsp;c&nbsp;<<&nbsp;endl;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;}