题干：
小乐乐一天天就知道玩，这一天又想玩象棋。
我们都知道马走日。
现在给定一个棋盘，大小是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，，但是可能有个问题就是可能搜索的范围会大了很多啊。。
京公网安备 11010502036488号