https://ac.nowcoder.com/acm/contest/301/F

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

小乐乐一天天就知道玩，这一天又想玩象棋。
我们都知道马走日。
现在给定一个棋盘，大小是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

输入

4 4 2

输出

2

解题思路

直接暴力，用dp[i][x][y]记录第i步走到x,y位置的方案数，则可用它来求出其八个方向的方案数。

#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int dp[205][205][205];
int next[8][2] = {{-2, -1}, {-2, 1}, {2, 1}, {2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
int main() {
    int n, m, k, tx, ty, ans;
    while (~scanf("%d%d%d", &n, &m, &k)) {
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for (int t = 1; t <= k; t++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < m; y++) {
                    if (dp[t - 1][x][y]) {
                        for (int k = 0; k < 8; k++) {
                            tx = x + next[k][0];
                            ty = y + next[k][1];
                            if (tx < 0 || tx >= n || ty < 0 || ty >= m)
                                continue;
                            dp[t][tx][ty] = (dp[t][tx][ty] + dp[t - 1][x][y]) % MOD;
                        }
                    }
                }
            }
        }
        printf("%d\n", dp[k][n - 1][m - 1]);
    }
    return 0;
}