象棋中“马”从某个位置（0,0）出发，经过K步，落在（x,y）上，有多少种方法

曾经终败给现在 2022-10-11 00:49 11阅读 0赞

描述：假设把整个棋盘放入第一象限，棋盘的最左下角是（0,0）位置，整个棋盘就是横坐标上9条线，纵坐标上10条线的区域，给出三个参数x,y,k；返回“马”从(0,0)位置出发，必须走K步，最终落在（x,y）上的方法数有多少种？

比如：K = 10;x = 7;y = 7  ,返回多少种方法？

解决方案：暴力递归和动态规划的思路去解决问题

1、暴力递归

1.1、图示分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

马在一个位置可以有八种选择，总之，加到一起就可以了。

1.2核心代码分析：

public class NanDaoHorseJump {
        public static void main(String[] args) {
            int x = 7;
            int y = 7;
            int step = 10;
            System.out.println(jumpWays1(x, y, step));
        }
    
        /**
         * 当前来到的位置是（x,y）
         * 	还剩下rest步需要跳
         * 跳完rest步，正好跳到a，b的方法数是多少？
         * 	10 * 9
         * @param k
         * @return
         */
        private static int jumpWays1(int a, int b, int k) {
            return j1(0,0,k,a,b);
        }
    
        private static int j1(int x, int y, int rest, int a, int b) {
            if(x < 0 || x > 9 || y < 0 || y > 8){
                return 0;
            }
            if(rest == 0){
                return (x == a && y == b)? 1 : 0;
            }
            //马跳的8种情况相加
            int ways = j1(x - 1,y + 2,rest - 1,a,b);
            ways += j1(x - 1,y - 2,rest - 1,a,b);
            ways += j1(x - 2,y + 1,rest - 1,a,b);
            ways += j1(x - 2,y - 1,rest - 1,a,b);
            ways += j1(x + 1,y - 2,rest - 1,a,b);
            ways += j1(x + 1,y + 2,rest - 1,a,b);
            ways += j1(x + 2,y + 1,rest - 1,a,b);
            ways += j1(x + 2,y - 1,rest - 1,a,b);
            return ways;
        }
    
    }

2、动态规划

2.1、三维数组图示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

有默认值，x轴和y轴之间，标准动态规划思想

2.2、过程图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

2.3、核心代码如下：

public class NanDaoHorseJump {
        public static void main(String[] args) {
            int x = 7;
            int y = 7;
            int step = 10;
            System.out.println(jumpWays2(x, y, step));
        }
    
        /**
         * 当前来到的位置是（x,y）
         * 	还剩下rest步需要跳
         * 跳完rest步，正好跳到a，b的方法数是多少？
         * 	10 * 9
         * @param k
         * @return
         */
        private static int jumpWays2(int a, int b, int k) {
            int[][][] dp = new int[10][9][k + 1];
            dp[a][b][0] = 1;
            for(int rest = 1;rest <= k;rest++){
                for(int x = 0;x < 10;x++){
                    for(int y = 0;y < 9;y++){
                        //马跳的8种情况相加
                        int ways = j2(dp,x + 2,y + 1,rest - 1);
                        ways += j2(dp,x + 2,y - 1,rest - 1);
                        ways += j2(dp,x + 1,y - 2,rest - 1);
                        ways += j2(dp,x + 1,y + 2,rest - 1);
                        ways += j2(dp,x - 2,y - 1,rest - 1);
                        ways += j2(dp,x - 2,y + 1,rest - 1);
                        ways += j2(dp,x - 1,y + 2,rest - 1);
                        ways += j2(dp,x - 1,y - 2,rest - 1);
                        dp[x][y][rest] = ways;
                    }
                }
            }
            return dp[0][0][k];
        }
    
        private static int j2(int[][][] dp, int x, int y, int rest) {
            if(x < 0|| x > 9 || y < 0 || y > 8){
                return 0;
            }
            return dp[x][y][rest];
        }
    
    }

两个方案执行结果如下：

![20210629170552259.png][]

到此，该到算法分享完毕，后期会有更多的解决方案和大家分享，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/2b7f0eeb54614768be4e2b62ea50704d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221005/1c9b49a1698a48b8be39777b583f69ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: /images/20221005/35e4f78a8c5d4256a52afef0b3878b38.png
[20210629170552259.png]: /images/20221005/fc42e9f327fe4e729527cfe62af2efd4.png