11package com .fishercoder .solutions ;
22
3- /**
4- * 935. Knight Dialer
5- *
6- * A chess knight can move as indicated in the chess diagram below:
7- *
8- * https://assets.leetcode.com/uploads/2018/10/12/knight.png
9- *
10- * |---|---|---|
11- * | 1 | 2 | 3 |
12- * |---|---|---|
13- * | 4 | 5 | 6 |
14- * |---|---|---|
15- * | 7 | 8 | 9 |
16- * |---|---|---|
17- * | x | 0 | x |
18- * |---|---|---|
19- *
20- * This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops.
21- * Each hop must be from one key to another numbered key.
22- *
23- * 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.
24- *
25- * How many distinct numbers can you dial in this manner?
26- *
27- * Since the answer may be large, output the answer modulo 10^9 + 7.
28- *
29- * Note:
30- * * 1 <= N <= 5000
31- */
32-
333public class _935 {
344/*
355 * The intuition is to calculate the number of ways
@@ -50,9 +20,9 @@ public static class Solution1 {
5020
5121// whereFromHere[i] is an array of keys that can be reached from the ith digit
5222private static final int [][]whereFromHere = {
53- {4 ,6 },6 ,8 },7 ,9 },4 ,8 },// 0, 1, 2, 3
54- {3 ,9 ,0 }, {},1 ,7 ,0 },// 4, 5, 6
55- {2 ,6 },1 ,3 },2 ,4 }// 7, 8, 9
23+ 4 ,6 }, {6 ,8 }, {7 ,9 }, {4 ,8 },// 0, 1, 2, 3
24+ 3 ,9 ,0 }, {}, {1 ,7 ,0 },// 4, 5, 6
25+ 2 ,6 }, {1 ,3 }, {2 ,4 }// 7, 8, 9
5626 };
5727
5828public int knightDialer (int N ) {