题目链接:https://ac.nowcoder.com/acm/contest/301/F
记忆化搜索,但是比赛的时候没去写....
AC代码:
#include <bits/stdc++.h>
#define maxn 205
#define ll long long
const int mod = 1000000007;
using namespace std;
ll dp[maxn][maxn][maxn];
int dir[8][2] = {1,2, 1,-2, -1,2, -1,-2, 2,1, 2,-1, -2,-1, -2,1};
int n,m,k;
bool Check(int x,int y){
if(x >= 0 && x < n && y >= 0 && y < m)return true;
return false;
}
int dfs(int x,int y,int step){
if(dp[x][y][step] != -1) return dp[x][y][step];
if(step == k){
if(x == n - 1 && y == m - 1) return 1;
else return 0;
}
ll sum = 0;
for(int i=0;i<8;i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(Check(xx, yy)){
sum += dfs(xx, yy, step + 1);
sum %= mod;
}
}
dp[x][y][step] = sum;
return sum;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&k)){
memset(dp,-1,sizeof(dp));
ll ans = dfs(0,0,0);
printf("%lld\n",ans);
}
return 0;
}