Skip to content

935. Knight Dialer 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  int knightDialer(int n) {
    constexpr int kDirs[8][2] = {{1, 2},   {2, 1},   {2, -1}, {1, -2},
                                 {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
    constexpr int kMod = 1'000'000'007;

    // dp[i][j] := the number 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] : kDirs) {
            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 = std::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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
  public int knightDialer(int n) {
    final int[][] DIRS = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
    final int MOD = 1_000_000_007;
    // dp[i][j] := the number of ways to stand on (i, j)
    int[][] dp = new int[4][3];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, 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]) % MOD;
          }
        }
      dp = newDp;
    }

    int ans = 0;

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

    return ans;
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def knightDialer(self, n: int) -> int:
    DIRS = ((1, 2), (2, 1), (2, -1), (1, -2),
            (-1, -2), (-2, -1), (-2, 1), (-1, 2))
    MOD = 1_000_000_007

    # dp[i][j] := the number 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]) % MOD
      dp = newDp

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