随笔记录

递归DP-中国象棋马跳到目标位置的走法

2022-6-5 diaba 笔试题

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));
    }
}