哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级）F. 小乐乐下象棋(记忆化搜索)

#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;
}