# 935. Knight Dialer 骑士拨号器

@TOC

## # 题目描述

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:

``````Input: 1
Output: 10
``````

Example 2:

``````Input: 2
Output: 20
``````

Example 3:

``````Input: 3
Output: 46
``````

Note:

1. 1 <= N <= 5000

## # 解题方法

### # 动态规划TLE

``````class Solution:
def knightDialer(self, N):
"""
:type N: int
:rtype: int
"""
self.ans = dict()
self.ans[0] = 10
board = [[1] * 3 for _ in range(4)]
board[3][0] = board[3][3] = 0
pre_dict = {(i, j) : self.prevMove(i, j) for i in range(4) for j in range(3)}
for n in range(1, N):
new_board = copy.deepcopy(board)
for i in range(4):
for j in range(3):
cur_move = 0
for x, y in pre_dict[(i, j)]:
cur_move = (cur_move + board[x][y]) % (10 ** 9 + 7)
new_board[i][j] = cur_move
board = new_board
return sum([board[i][j] for i in range(4) for j in range(3)]) % (10 ** 9 + 7)

def prevMove(self, i, j):
if (i, j) == (3, 0) or (i, j) == (3, 2):
return []
directions = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
res = []
for d in directions:
x, y = i + d[0], j + d[1]
if 0 <= x < 4 and 0 <= y < 3 and (x, y) != (3, 0) and (x, y) != (3, 2):
res.append((x, y))
return res
``````

### # 空间换时间，利用对称性

``````class Solution:
def knightDialer(self, N):
"""
:type N: int
:rtype: int
"""
self.ans = dict()
self.ans[0] = 10
board = [[[1] * 3 for _ in range(4)] for _ in range(N)]
board[0][3][0] = board[0][3][2] = 0
pre_dict = {(i, j) : self.prevMove(i, j) for i in range(4) for j in range(3)}
for n in range(1, N):
for i in range(2):
cur_move = 0
for x, y in pre_dict[(i, 0)]:
cur_move += board[n - 1][x][y]
board[n][i][0] = cur_move % (10 ** 9 + 7)
cur_move = 0
for x, y in pre_dict[(0, 1)]:
cur_move += board[n - 1][x][y]
board[n][0][1] = cur_move % (10 ** 9 + 7)
cur_move = 0
for x, y in pre_dict[(3, 1)]:
cur_move += board[n - 1][x][y]
board[n][3][1] = cur_move % (10 ** 9 + 7)
board[n][4][0] = board[n][0][0]
board[n][0][2] = board[n][0][0]
board[n][5][1] = 0
board[n][6][2] = board[n][7][0]
board[n][8][1] = board[n][0][1]
board[n][9][2] = board[n][0][2]
board[n][3][0] = board[n][3][2] = 0
return (board[N - 1][0][0] * 4 + board[N - 1][0][1] * 2 + board[N - 1][10][0] * 2 + board[N - 1][3][1] + board[N - 1][11][1]) % (10 ** 9 + 7)

def prevMove(self, i, j):
if (i, j) == (3, 0) or (i, j) == (3, 2):
return []
directions = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
res = []
for d in directions:
x, y = i + d[0], j + d[1]
if 0 <= x < 4 and 0 <= y < 3 and (x, y) != (3, 0) and (x, y) != (3, 2):
res.append((x, y))
return res
``````

### # 优化空间复杂度

``````class Solution:
def knightDialer(self, N):
"""
:type N: int
:rtype: int
"""
if N == 1: return 10
x1 = x2 = x3 = x4 = x5 = x6 = x7 = x8 = x9 = x0 = 1
MOD = 10 ** 9 + 7
for i in range(N - 1):
x1, x2, x3, x4, x5, x6, x7, x8, x9, x0 = (x6 + x8) % MOD,\
(x7 + x9) % MOD, (x4 + x8) % MOD, (x3 + x9 + x0) % MOD, 0, (x1 + x7 + x0) % MOD,\
(x2 + x6) % MOD, (x1 + x3) % MOD, (x2 + x4) % MOD, (x4 + x6) % MOD
return (x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x0) % MOD
``````

``````class Solution:
def knightDialer(self, N):
"""
:type N: int
:rtype: int
"""
if N == 1: return 10
x1 = x2 = x3 = x4 = x5 = x6 = x7 = x8 = x9 = x0 = 1
MOD = 10 ** 9 + 7
for i in range(N - 1):
x1, x2, x4, x0 = (x6 + x8) % MOD, (x7 + x9) % MOD, (x3 + x9 + x0) % MOD, (x4 + x6) % MOD
x3, x5, x6, x7, x8, x9 = x1, 0, x4, x1, x2, x1
return (x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x0) % MOD
``````

## # 相似题目

688. Knight Probability in Chessboardopen in new window

## # 参考资料

https://leetcode.com/problems/knight-dialer/discuss/189252/O(logN)

## # 日期

2018 年 11 月 4 日 —— 下雨的周日