package com.jiucaiyuan.net.question;



/**

 * 中国象棋

 *

 * @Author jiucaiyuan  2022/6/5 17:43

 * @mail services@jiucaiyuan.net

 */



public class ChineseChessHorseJump {

    /**

     * 象棋，马从(0,0)位置，跳step步到达(x,y)位置的方法数

     *

     * @param x    目的地x轴坐标

     * @param y    目的地y轴坐标

     * @param step 跳次数（步数）

     * @return 返回方法数

     */

    public static int horse2DestinationWays(int x, int y, int step) {

        return process(x, y, step);

    }



    /**

     * 代码实现是从(x,y)跳到(0,0)的方法数，和题目一样

     *

     * @param x

     * @param y

     * @param step

     * @return

     */

    private static int process(int x, int y, int step) {

        if (x < 0 || x > 8 || y < 0 || y > 9) {

            //入参不合法时，直接返回方法数为0

            return 0;

        }

        if (step == 0) {

            return (x == 0 && y == 0) ? 1 : 0;

        }

        return process(x - 1, y + 2, step - 1)

                + process(x + 1, y + 2, step - 1)

                + process(x + 2, y + 1, step - 1)

                + process(x + 2, y - 1, step - 1)

                + process(x + 1, y - 2, step - 1)

                + process(x - 1, y - 2, step - 1)

                + process(x - 2, y - 1, step - 1)

                + process(x - 2, y + 1, step - 1)

                ;

    }



    /**

     * @param x

     * @param y

     * @param step

     * @return

     */

    public static int dpWays(int x, int y, int step) {

        if (x < 0 || x > 8 || y < 0 || y > 9) {

            //入参不合法时，直接返回方法数为0

            return 0;

        }

        int[][][] dp = new int[9][10][step + 1];

        dp[0][0][0] = 1;

        //从第一层开始，逐渐尝试到step层

        for (int h = 1; h <= step; h++) {

            for (int r = 0; r < 9; r++) {  //同一层顺序无所谓，也可以按照r降序尝试

                for (int c = 0; c < 10; c++) { //同一层顺序无所谓，也可以按照c降序尝试

                    dp[r][c][h] += getValue(dp, r - 1, c + 2, h - 1);

                    dp[r][c][h] += getValue(dp, r + 1, c + 2, h - 1);

                    dp[r][c][h] += getValue(dp, r + 2, c + 1, h - 1);

                    dp[r][c][h] += getValue(dp, r + 2, c - 1, h - 1);

                    dp[r][c][h] += getValue(dp, r + 1, c - 2, h - 1);

                    dp[r][c][h] += getValue(dp, r - 1, c - 2, h - 1);

                    dp[r][c][h] += getValue(dp, r - 2, c - 1, h - 1);

                    dp[r][c][h] += getValue(dp, r - 2, c + 1, h - 1);

                }

            }

        }

        return dp[x][y][step];

    }



    private static int getValue(int[][][] dp, int row, int col, int step) {

        if (row < 0 || row > 8 || col < 0 || col > 9) {

            //入参不合法时，直接返回方法数为0

            return 0;

        }

        return dp[row][col][step];

    }



    public static void main(String[] args) {

        int x = 7;

        int y = 7;

        int step = 10;

        System.out.println(horse2DestinationWays(x, y, step));

        System.out.println(dpWays(x, y, step));

    }

}