LeetCode Solutions

			

class Solution {
 public:
  int knightDialer(int n) {
    constexpr int kMod = 1'000'000'007;
    const vector<pair<int, int>> dirs = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1},
                                         {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

    // dp[i][j] := # of ways to stand on (i, j)
    vector<vector<int>> dp(4, vector<int>(3, 1));
    dp[3][0] = dp[3][2] = 0;

    for (int k = 0; k < n - 1; ++k) {
      vector<vector<int>> newDp(4, vector<int>(3));
      for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 3; ++j) {
          if (isNotNumericCell(i, j))
            continue;
          for (const auto& [dx, dy] : dirs) {
            const int x = i + dx;
            const int y = j + dy;
            if (x < 0 || x >= 4 || y < 0 || y >= 3)
              continue;
            if (isNotNumericCell(x, y))
              continue;
            newDp[i][j] = (newDp[i][j] + dp[x][y]) % kMod;
          }
        }
      dp = move(newDp);
    }

    int ans = 0;

    for (const vector<int>& row : dp)
      for (const int a : row)
        ans = (ans + a) % kMod;

    return ans;
  }

 private:
  bool isNotNumericCell(int i, int j) {
    return i == 3 && (j == 0 || j == 2);
  }
};

			

class Solution {
  public int knightDialer(int n) {
    final int kMod = 1_000_000_007;
    final int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
    // dp[i][j] := # of ways to stand on (i, j)
    int[][] dp = new int[4][3];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, 1));
    dp[3][0] = dp[3][2] = 0;

    for (int k = 0; k < n - 1; ++k) {
      int[][] newDp = new int[4][3];
      for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 3; ++j) {
          if (isNotNumericCell(i, j))
            continue;
          for (int[] dir : dirs) {
            final int x = i + dir[0];
            final int y = j + dir[1];
            if (x < 0 || x >= 4 || y < 0 || y >= 3)
              continue;
            if (isNotNumericCell(x, y))
              continue;
            newDp[i][j] = (newDp[i][j] + dp[x][y]) % kMod;
          }
        }
      dp = newDp;
    }

    int ans = 0;

    for (int[] row : dp)
      for (final int a : row)
        ans = (ans + a) % kMod;

    return ans;
  }

  private boolean isNotNumericCell(int i, int j) {
    return i == 3 && (j == 0 || j == 2);
  }
}

			

class Solution:
  def knightDialer(self, n: int) -> int:
    kMod = 1_000_000_007
    dirs = [(-2, 1), (-1, 2), (1, 2), (2, 1),
            (2, -1), (1, -2), (-1, -2), (-2, -1)]

    # dp[i][j] := # Of ways stand on (i, j)
    dp = [[1] * 3 for _ in range(4)]
    dp[3][0] = dp[3][2] = 0

    for _ in range(n - 1):
      newDp = [[0] * 3 for _ in range(4)]
      for i in range(4):
        for j in range(3):
          if (i, j) in ((3, 0), (3, 2)):
            continue
          for dx, dy in dirs:
            x = i + dx
            y = j + dy
            if x < 0 or x >= 4 or y < 0 or y >= 3:
              continue
            if (x, y) in ((3, 0), (3, 2)):
              continue
            newDp[x][y] = (newDp[x][y] + dp[i][j]) % kMod
      dp = newDp

    return sum(map(sum, dp)) % kMod