首页 > 试题广场 >

象棋中马的跳法

[编程题]象棋中马的跳法

热度指数：829 时间限制：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

输出

算法知识视频讲解

Java

Ba.St.p

递归和动态规划两种解法

递归解法容易理解，动态规划效率更高

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)