c++DFS算法問題
2 回答
長風秋雁
TA貢獻1757條經驗 獲得超7個贊
這個題是比較基本的DFS問題，建議你自己多看多試一下，自己做出來意義更大一點。我想提供給你另外一種思路，時間復雜度更低，對于每個坐標（X，Y）可以從（x-1，y）和（x，y-1）到達，所以到這一點的可能數就是到達兩個先驅點的方案數量的和，把黑洞設置成0就行了
阿晨1998
TA貢獻2037條經驗 獲得超6個贊
| 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;} |
- 2 回答
- 0 關注
- 858 瀏覽
添加回答
舉報
0/150
提交
取消