c++DFS算法问题?

Question

c++DFS算法问题

Answer 1

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

Answer 2

1234567891011121314151617181920212223242526272829303132

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