2. /**
    3.  * 跳马问题：
    4.  * 把象棋棋盘放在第一象限位置，棋盘的最左下角位置是(0,0),那么整个棋盘就是横坐标上九条线，纵坐标上十条线的区域
    5.  * 给定三个参数，x,y,k
    6.  * 返回马从（0，0）位置出发，必须走K步，最后落在（x,y）上的方法数有多少个。
    7.  */
    8. public class Code02_HorseJump {
    10. // #############################方式一，暴力递归#####################################################
    11.     // 10 * 9
    12.     // 主函数
    13.     public static int jump(int a, int b, int k) {
    14.         return process(0, 0, k, a, b);
    15.     }
    17.     // 当前来到的位置是（x,y）
    18.     // 还剩下rest步需要跳
    19.     // 跳完rest步，正好跳到a，b的方法数是多少？
    20.     public static int process(int x, int y, int rest, int a, int b) {
    21.         // 跳出棋盘返回0
    22.         if (x < 0 || x > 9 || y < 0 || y > 8) {
    23.             return 0;
    24.         }
    26.         if (rest == 0) {
    27.             return (x == a && y == b) ? 1 : 0;
    28.         }
    29.         // x,y位置下一步八个方向上跳法的方法数总和。
    30.         int ways = process(x + 2, y + 1, rest - 1, a, b);
    31.         ways += process(x + 1, y + 2, rest - 1, a, b);
    32.         ways += process(x - 1, y + 2, rest - 1, a, b);
    33.         ways += process(x - 2, y + 1, rest - 1, a, b);
    34.         ways += process(x - 2, y - 1, rest - 1, a, b);
    35.         ways += process(x - 1, y - 2, rest - 1, a, b);
    36.         ways += process(x + 1, y - 2, rest - 1, a, b);
    37.         ways += process(x + 2, y - 1, rest - 1, a, b);
    38.         return ways;
    39.     }
    40. // #############################方式二，动态规划#####################################################
    42.     // *Note*：对于这种三维，有三个动态参数的。如果关系依赖简单，则可以进行优化，改成动态规划的形式。如果关系依赖复杂，直接使用记忆化搜索（缓存法）无需修改。
    44.     // dp解决  三维， xy为底，rest为高。通过第0层，可以推出第一层，第i层的位置依赖的是i-1层的。同一层没有依赖关系。rest==0即第0层的时候
    45.     // 只有 a,b位置是1，其他都为0，则第一层所有数据确定，然后可以得到第二层的数据，依次向上。
    46.     public static int dp(int a, int b, int k) {
    47.         int[][][] dp = new int[10][9][k + 1];
    48.         // 第0层
    49.         dp[a][b][0] = 1;
    50.         // 1-K层
    51.         for (int rest = 1; rest <= k; rest++) {  // 最外层for循环表示 有多少层。
    52.             for (int x = 0; x < 10; x++) {       // 里面两个for循环，穷举，x,y的值。
    53.                 for (int y = 0; y < 9; y++) {
    54.                     int ways = pick(dp, x + 2, y + 1, rest - 1);
    55.                     ways += pick(dp, x + 1, y + 2, rest - 1);
    56.                     ways += pick(dp, x - 1, y + 2, rest - 1);
    57.                     ways += pick(dp, x - 2, y + 1, rest - 1);
    58.                     ways += pick(dp, x - 2, y - 1, rest - 1);
    59.                     ways += pick(dp, x - 1, y - 2, rest - 1);
    60.                     ways += pick(dp, x + 1, y - 2, rest - 1);
    61.                     ways += pick(dp, x + 2, y - 1, rest - 1);
    62.                     dp[x][y][rest] = ways;
    63.                 }
    64.             }
    65.         }
    66.         return dp[0][0][k];
    67.     }
    69.     // 获取x,y.rest位置的值，越界返回0.
    70.     public static int pick(int[][][] dp, int x, int y, int rest) {
    71.         if (x < 0 || x > 9 || y < 0 || y > 8) {
    72.             return 0;
    73.         }
    74.         return dp[x][y][rest];
    75.     }
    77. // #################################################################################
    78.     public static int ways(int a, int b, int step) {
    79.         return f(0, 0, step, a, b);
    80.     }
    82.     public static int f(int i, int j, int step, int a, int b) {
    83.         if (i < 0 || i > 9 || j < 0 || j > 8) {
    84.             return 0;
    85.         }
    86.         if (step == 0) {
    87.             return (i == a && j == b) ? 1 : 0;
    88.         }
    89.         return f(i - 2, j + 1, step - 1, a, b) + f(i - 1, j + 2, step - 1, a, b) + f(i + 1, j + 2, step - 1, a, b)
    90.                 + f(i + 2, j + 1, step - 1, a, b) + f(i + 2, j - 1, step - 1, a, b) + f(i + 1, j - 2, step - 1, a, b)
    91.                 + f(i - 1, j - 2, step - 1, a, b) + f(i - 2, j - 1, step - 1, a, b);
    93.     }
    95.     public static int waysdp(int a, int b, int s) {
    96.         int[][][] dp = new int[10][9][s + 1];
    97.         dp[a][b][0] = 1;
    98.         for (int step = 1; step <= s; step++) { // 按层来
    99.             for (int i = 0; i < 10; i++) {
    100.                 for (int j = 0; j < 9; j++) {
    101.                     dp[i][j][step] = getValue(dp, i - 2, j + 1, step - 1) + getValue(dp, i - 1, j + 2, step - 1)
    102.                             + getValue(dp, i + 1, j + 2, step - 1) + getValue(dp, i + 2, j + 1, step - 1)
    103.                             + getValue(dp, i + 2, j - 1, step - 1) + getValue(dp, i + 1, j - 2, step - 1)
    104.                             + getValue(dp, i - 1, j - 2, step - 1) + getValue(dp, i - 2, j - 1, step - 1);
    105.                 }
    106.             }
    107.         }
    108.         return dp[0][0][s];
    109.     }
    111.     // 在dp表中，得到dp[i][j][step]的值，但如果(i，j)位置越界的话，返回0；
    112.     public static int getValue(int[][][] dp, int i, int j, int step) {
    113.         if (i < 0 || i > 9 || j < 0 || j > 8) {
    114.             return 0;
    115.         }
    116.         return dp[i][j][step];
    117.     }
    119.     public static void test(int x){
    120.         x++;
    121.     }
    123.     public static void main(String[] args) {
    124.         Integer x = 7;
    125.         int y = 7;
    127.         test(x);
    128.         System.out.println(x);
    131.         int step = 10;
    132. //        System.out.println(ways(x, y, step));
    133. //        System.out.println(dp(x, y, step));
    134. //        System.out.println(jump(x, y, step));
    135.     }
    136. }