Description

国际象棋中的马放在一个拨号器的任意位置，求走\(n\)步后能生成多少个电话号码。

1 2 3
4 5 6
7 8 9
* 0 #

拨号器如上表所示（其中*和#不可用）。

knight

另外补充马的走法，如上图所示。

Constraints

\(1 \le n \le 5000\)

Solution

没啥意思的题目，思路见LeetCode-688，仅需消除后效性。

我本以为需要做一个转换表，比如\(convert[nums][8]\)表示数字\(nums\)能跳到哪里。其实是不需要的，因为电话上每个数字都是唯一的。

偶尔用点离谱的写法当题解吧。

Code

class Solution {
public:
    int knightDialer(int n) {
        constexpr int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
        constexpr int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};

        long dp[2][3][4] {};
        fill(&dp[0][0][0], &dp[1][0][0], 1);
        dp[0][0][3] = dp[0][2][3] = 0;

        auto for_d = [&](int i, int j, auto &&f) {
            for(auto d = 0; d < 8; ++d) {
                auto x = i + dx[d];
                auto y = j + dy[d];
                if(x < 0 || x >= 3) continue;
                if(y < 0 || y >= 4) continue;
                f(x, y);
            }
        };

        constexpr long MOD = 1e9 + 7;
        for(int step = 1; step < n; ++step) {
            auto zip = [](auto &i, auto &j) {++(j==3?j=0,i:j);};
            for(int i = 0, j = 0; i < 3; zip(i, j)) {
                dp[step &1][i][j] = 0;
                if(i == 0 && j == 3) continue;
                if(i == 2 && j == 3) continue;
                for_d(i, j, [&](auto x, auto y) {
                    dp[step &1][i][j] += dp[step-1 &1][x][y];
                    dp[step &1][i][j] %= MOD;
                });
            }
        }

        long sum = 0;
        for(auto &&vec : dp[n-1&1]) {
            sum = accumulate(begin(vec), end(vec), sum % MOD);
        }
        return sum % MOD;
    }
};

LeetCode-935 Knight Dialer