Description
国际象棋中的马放在一个拨号器的任意位置，求走\(n\)步后能生成多少个电话号码。
1 2 3
4 5 6
7 8 9
* 0 #
拨号器如上表所示（其中*和#不可用）。
另外补充马的走法，如上图所示。
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;
}
};