2019獨角獸企業重金招聘Python工程師標準>>>

/** E:踩方格查看 提交 統計 提問 總時間限制: 1000ms 內存限制: 65536kB 描述 有一個方格矩陣，矩陣邊界在無窮遠處。我們做如下假設： a. 每走一步時，只能從當前方格移動一格，走到某個相鄰的方格上； b. 走過的格子立即塌陷無法再走第二次； c. 只能向北、東、西三個方向走； 請問：如果允許在方格矩陣上走n步，共有多少種不同的方案。2種走法只要有一步不一樣，即被認為是不同的方案。輸入 允許在方格上行走的步數n(n <= 20) 輸出 計算出的方案數量 樣例輸入 2樣例輸出 7 dp做法： dp[n] = 2 * dp[n - 1] + dp[n - 2] 對于dp[n]顯然n-1的每一點都可以向北走一步，并且至少可以向東或向西一步。從n-2向北走得到的n-1既可向東又可向西。 所以狀態轉移方程就出來拉 以下是dfs 沒參考價值= = 建議無視*/ #include <cstdio> #include <list> using namespace std; bool used[42][42] = {0}; int sum = 0;void dfs(int a, int b, int c) {if(used[a][b]) return;if(c == 0) {sum++;return;}used[a][b] = 1;dfs(a - 1, b, c - 1);dfs(a, b - 1, c - 1);dfs(a, b + 1, c - 1);used[a][b] = 0;return; }int main() {sum = 0;int n = 0;scanf("%d", &n);dfs(20,20, n);printf("%d\n", sum); }

轉載于:https://my.oschina.net/locusxt/blog/137016

總結

以上是生活随笔為你收集整理的poj 踩方格的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。