首页 > 试题广场 > 象棋中马的跳法
[编程题]象棋中马的跳法
  • 热度指数:114 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
请同学们自行搜索或者想象一个象棋的棋盘,然后把整个棋盘放入第一象限,棋盘的最左下 角是(0,0)位置。那么整个棋盘就是横坐标上9条线、纵坐标上10条线的一个区域。给你三个参数,x,y,k,返回如果“马”从(0,0)位置出发,必须走k步,最后落在(x,y)上的方法数 有多少种?

输入描述:
输入一行数字,包含3个参数x,y,k


输出描述:
输出一个数,代表有几种
示例1

输入

7 7 10

输出

515813
递归和动态规划两种解法
递归解法容易理解,动态规划效率更高
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int k = scanner.nextInt();
        
        System.out.print(waysdp(k, x, y) + "");
    }
    
    // 动态规划
    public static int waysdp(int k, int x, int y){
        int[][][] dp = new int[9][10][k + 1];
        // 达成条件
        dp[x][y][0] = 1;
        for(int rest = 1; rest < k + 1; rest++){
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 10; j++){
                    dp[i][j][rest] = (getValue(dp, i - 1, j - 2, rest - 1) + 
                        getValue(dp, i - 2, j - 1, rest - 1) + 
                        getValue(dp, i - 1, j + 2, rest - 1) + 
                        getValue(dp, i - 2, j + 1, rest - 1) + 
                        getValue(dp, i + 1, j - 2, rest - 1) + 
                        getValue(dp, i + 2, j - 1, rest - 1) + 
                        getValue(dp, i + 1, j + 2, rest - 1) + 
                        getValue(dp, i + 2, j + 1, rest - 1));
                }
            }
        }
        return dp[0][0][k];
    }
    
    public static int getValue(int[][][] dp, int a, int b, int rest){
        if(a > 8 || a < 0 || b > 9 || b < 0) {
            return 0;
        }
        return dp[a][b][rest];
    }
    
    public static int recursion(int a , int b, int rest, int x, int y){
        if(a > 8 || a < 0 || b > 9 || b < 0) {
            return 0;
        }
        if(rest == 0){
            return  a == x && b == y ? 1 : 0;
        }

        return recursion(a - 1, b - 2, rest -1, x, y) + 
            recursion(a - 2, b - 1, rest -1, x, y) + 
            recursion(a - 1, b + 2, rest -1, x, y) + 
            recursion(a - 2, b + 1, rest -1, x, y) + 
            recursion(a + 1, b - 2, rest -1, x, y) + 
            recursion(a + 2, b - 1, rest -1, x, y) + 
            recursion(a + 1, b + 2, rest -1, x, y) + 
            recursion(a + 2, b - 1, rest -1, x, y);
    }
    
}

编辑于 2021-04-28 17:22:23 回复(0)