LeetCode 935. Knight Dialer

, , ,

Question

A chess knight can move as indicated in the chess diagram below:

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops. Each hop must be from one key to another numbered key.

Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.

How many distinct numbers can you dial in this manner?

Since the answer may be large, output the answer modulo 10^9 + 7.

Example

1
2
3
4
5
6
7
8
Input: 1
Output: 10

Input: 2
Output: 20

Input: 3
Output: 46

Solution

Intuition: we need to search different ways in N steps, so we have to use DFS first and then memo it.

For the memo part, which information we need to care? I think it should be row(i), col(j), and count.

Code

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
public int MOD;
    int[][][] memo;
    // time:O(10N) space:O(N * 4 * 3)
    public int knightDialer(int N) {
        int res  = 0;
        memo = new int[N + 1][4][3];
        MOD = (int) Math.pow(10, 9) + 7;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 3; j++) {
                res = (dfs(N, i, j, 1) + res) % MOD;
            }
        }
        return res;
    }
    
    public int dfs(int N, int i, int j, int count) {
        if (i < 0 || i >= 4 || j < 0 || j >= 3 || (i == 3 && j != 1)) return 0;
        if (count == N) return 1;
        if (memo[count][i][j] > 0) return memo[count][i][j];
        int[][] dirs = {{2, 1}, {1, 2}, {2, -1}, {1, -2},
                        {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1}};
        int res = 0;
        for (int[] dir : dirs) {
            res = (res + dfs(N, i + dir[0], j + dir[1], count + 1)) % MOD; 
        }
        memo[count][i][j] = res;
        return res;
    }