題干：
?

小樂樂一天天就知道玩，這一天又想玩象棋。
我們都知道馬走日。
現在給定一個棋盤，大小是n*m,把棋盤放在第一象限，棋盤的左下角是(0,0),右上角是(n - 1, m - 1);
小樂樂想知道，一個馬從左下角(0, 0)開始，走了k步之后，剛好走到右上角(n - 1, m - 1)的方案數。

輸入描述:

輸入：多組樣例輸入，每組一行，三個整數n, m, k(1 <= n, m, k <= 200),如題目所示。

輸出描述:

輸出：輸出答案 mod 1000000007

示例1

輸入

復制

4 4 2

輸出

復制

2

解題報告：

? ?跪了一晚上發現是因為寫成了ty=x+ny[k]了，，，看來是太久不寫地圖的dfs了、、老毛病又犯了、、難受難受

AC代碼1：（記憶化搜索）

? 其實也可以直接在main函數中dp[n][m][0]=1，這樣在寫dfs的時候就不需要特判一下出口了、、總的來說是個不算難的好題、、

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll dp[205][205][205]; const ll mod = 1000000007; int n,m,t; int nx[9] = {-2,-1,1,2,2,1,-1,-2}; int ny[9] = {1,2,2,1,-1,-2,-2,-1}; bool ok(int x,int y) {if(x>=1&&x<=n&&y>=1&&y<=m) return 1;else return 0; } ll dfs(int x,int y,int res) {if(x == n && y == m && res == 0) return dp[n][m][res]=1;if(res <= 0) return 0;if(dp[x][y][res]!=-1) return dp[x][y][res];ll sum = 0;int tx,ty;for(int k = 0; k<8; k++) {tx = x + nx[k];ty = y + ny[k];if(ok(tx,ty) == 0) continue;//if(res==0) continue;sum += dfs(tx,ty,res-1);sum %= mod;}dp[x][y][res] = sum;return sum;} int main() {while(~scanf("%d%d%d",&n,&m,&t)) {memset(dp,-1,sizeof dp);printf("%lld\n",dfs(1,1,t)%mod);} return 0 ;}

其中也有一個細節值得注意，，這樣搜索的正確性，，首先因為你表示的狀態，體現出了剩余的步數，所以不用怕走過去下一步又走回來這種情況，，因為在狀態設計中這屬于不同的狀態，，所以沒事，，再就是不用怕會出現環，，也就是繞一圈狀態又繞回來了。。原因就是因為你的dfs都是res-1的操作，所以整個就是一個DAG圖，不必要擔心會出現未完成值的重復調用。。

AC代碼2：（三種直接dp）

#include<bits/stdc++.h> using namespace std; #define LL long long #define pii pair<int,int> #define x first #define y second #define mp make_pair //#define debug const LL mod=1e9+7; LL f[205][205][205]; int fx[8][2]={1,2,1,-2,2,1,2,-1,-1,-2,-1,2,-2,-1,-2,1}; void B(){int n,m,K;while(cin>>n>>m>>K){memset(f,0,sizeof(f));f[1][1][0]=1;for(int k=0;k<=K;++k){for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(f[i][j][k]){for(int o=0;o<8;++o){if(i+fx[o][0]>=1 && j+fx[o][1]>=1)(f[i+fx[o][0]][j+fx[o][1]][k+1]+=f[i][j][k])%=mod; }}}}}cout<<f[n][m][K]<<endl;} } int main(){B();return 0; }#include<bits/stdc++.h> #define mod 1000000007 using namespace std; int dp[205][205][205]; int dis[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2}; int main() {int n,m,k;while(scanf("%d%d%d",&n,&m,&k)!=EOF){memset(dp,0,sizeof(dp));dp[1][1][0]=1;for(int s=1;s<=k;s++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int temp=0;for(int h=0;h<8;h++){int x=i+dis[h][0];int y=j+dis[h][1];if(x>=1&&x<=n&&y>=1&&y<=m)temp+=dp[x][y][s-1],temp%=mod;}dp[i][j][s]=temp;}printf("%d\n",dp[n][m][k]); }return 0; }#include <bits/stdc++.h> using namespace std; int dp[205][205][205]; const int mod=1000000007; int nex[8][2]={{1,2},{2,1},{-1,-2},{-2,-1},{2,-1},{1,-2},{-1,2},{-2,1}}; int main() {int n,m,d;while(~scanf("%d %d %d",&n,&m,&d)){memset(dp,0,sizeof(dp));dp[1][1][0]=1;for(int k=1;k<=d;k++){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){for(int s=0;s<8;s++){int x=i+nex[s][0];int y=j+nex[s][1];if(x<1||y<1||x>n||y>m) continue;dp[i][j][k]=(dp[i][j][k]+dp[x][y][k-1])%mod;}}}printf("%d\n",dp[n][m][d]);}return 0; }

看了dp的代碼發現dp好像也不是很難寫、、、也不是很難想，，因為這種狀態也是符合遞推的。。

簡單的一個題，，著實又讓我對動態規劃有了新的理解！！！！

考慮改編：

? ? 改編成一個n*m的方格，但是終點不是右上角的那個[n,m]點，而是新輸入的兩個點，，這樣進行dp，，但是可能有個問題就是可能搜索的范圍會大了很多啊。。

總結

以上是生活随笔為你收集整理的【牛客 - 301哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）】小乐乐下象棋（记忆化搜索dp，dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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