象棋中的馬跳步問題

作者：Grey

原文地址：

部落格園：象棋中的馬跳步問題

CSDN：象棋中的馬跳步問題

題目描述

中國象棋中，整個棋盤就是橫座標上 9 條線、縱座標上 10 條線的一個區域，給你三個引數 x，y，k；返回『馬』從 (0,0) 位置出發，必須走 k 步；

最後落在 (x,y) 上的方法數有多少種?

題目連結見：牛客-象棋中馬的跳法

暴力解法

定義遞迴函數

int ways(int i, int j, int a, int b, int step)

遞迴含義表示：從 (i,j) 出發，到 (a,b) 且必須要走 step 步的情況下，有多少種走法。

接下來是 base case，首先 (i,j) 座標如果已經越界，說明不可能有有效走法，直接返回 -1。

(i, j) 越界的條件是

(i >= 10 || j >= 9 || i < 0 || j < 0)

如果 step == 0，說明沒有可走的步數了，此時，除非 (i == a && j == b) ，可以有一種走法（在原地不動），其他情況，都無路可走，返回 -1。

base case 程式碼如下

        // 象棋區域 int[][] area = new int[10][9]
        if (i >= 10 || j >= 9 || i < 0 || j < 0) {
            // 越界
            return -1;
        }
        if (step == 0) {
            if (i == a && j == b) {
                return 1;
            }
            return -1;
        }

接下來就是普遍情況，『馬』可以四面八方嘗試

    // 四面八方嘗試
        int p1 = ways(i - 2, j + 1, a, b, step - 1);
        int p2 = ways(i - 1, j + 2, a, b, step - 1);
        int p3 = ways(i - 1, j - 2, a, b, step - 1);
        int p4 = ways(i - 2, j - 1, a, b, step - 1);
        int p5 = ways(i + 2, j + 1, a, b, step - 1);
        int p6 = ways(i + 1, j + 2, a, b, step - 1);
        int p7 = ways(i + 1, j - 2, a, b, step - 1);
        int p8 = ways(i + 2, j - 1, a, b, step - 1);

返回這些情況的合計即可。

暴力解法完整程式碼如下

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int y = in.nextInt();
        int k = in.nextInt();
        System.out.println(ways(0,0,x, y, k));
        in.close();
    }

    // 遞迴含義：還剩下step步，從(i,j)到達(a，b)可以選擇的方法數是多少
    public static int ways(int i, int j, int a, int b, int step) {
        // 象棋區域 int[][] area = new int[10][9]
        if (i >= 10 || j >= 9 || i < 0 || j < 0) {
            // 越界
            return -1;
        }
        if (step == 0) {
            if (i == a && j == b) {
                return 1;
            }
            return -1;
        }
        // 四面八方嘗試
        int p1 = ways(i - 2, j + 1, a, b, step - 1);
        int p2 = ways(i - 1, j + 2, a, b, step - 1);
        int p3 = ways(i - 1, j - 2, a, b, step - 1);
        int p4 = ways(i - 2, j - 1, a, b, step - 1);
        int p5 = ways(i + 2, j + 1, a, b, step - 1);
        int p6 = ways(i + 1, j + 2, a, b, step - 1);
        int p7 = ways(i + 1, j - 2, a, b, step - 1);
        int p8 = ways(i + 2, j - 1, a, b, step - 1);
        return ((p1 == -1) ? 0 : p1) + ((p2 == -1) ? 0 : p2) + ((p3 == -1) ? 0 : p3) + ((p4 == -1) ? 0 : p4) + ((p5 == -1) ? 0 : p5) + ((p6 == -1) ? 0 : p6) + ((p7 == -1) ? 0 : p7) + ((p8 == -1) ? 0 : p8);
    }
}

執行超時

動態規劃解（可 AC）

根據上述暴力遞迴過程可知，遞迴函數有三個可變引數，分別是 a，b，step，每個引數都有一定的範圍，所以可以利用一個三維陣列 dp 來囊括所有的遞迴過程的中間結果。

        // 象棋區域 int[][] area = new int[10][9]
        int[][][] dp = new int[10][9][step + 1];

其中dp[x][y][k]就表示遞迴函數ways(0,0,x,y,k)的結果。

基於暴力遞迴的 base case 可知

dp[a][b][0] = 1;

針對普遍情況，暴力遞迴過程的虛擬碼如下

    public static int ways(int i, int j, int a, int b, int step) {
        ……
        // 四面八方嘗試
        int p1 = ways(i - 2, j + 1, a, b, step - 1);
        int p2 = ways(i - 1, j + 2, a, b, step - 1);
        int p3 = ways(i - 1, j - 2, a, b, step - 1);
        int p4 = ways(i - 2, j - 1, a, b, step - 1);
        int p5 = ways(i + 2, j + 1, a, b, step - 1);
        int p6 = ways(i + 1, j + 2, a, b, step - 1);
        int p7 = ways(i + 1, j - 2, a, b, step - 1);
        int p8 = ways(i + 2, j - 1, a, b, step - 1);
        ……
    }

即 dp[i][j][step] 依賴 dp[i-2][j+1][step-1] ， dp[i-1][j+2][step-1] ，dp[i-1][j-2][step-1] ， dp[i-2][j-1][step-1] ，dp[i+2][j+1][step-1] ， dp[i+1][j+2][step-1] ，dp[i+1][j-2][step-1] ， dp[i+2][j-1][step-1] ，範例圖如下

如下圖，其中(i,j,step)座標上的點只依賴 step - 1 層上對應的八個點，而不依賴本層任意一點。

已知第 0 層已經填好了（上面已經提到 dp[a][b][0] = 1 ），所以，可以從 1 層開始，依次填好每一層。

動態規劃解完整程式碼如下


import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int y = in.nextInt();
        int k = in.nextInt();
        System.out.println(ways(x, y, k));
        in.close();
    }

    // 根據暴力遞迴改動態規劃
    public static int ways(int a, int b, int step) {
        // 象棋區域 int[][] area = new int[10][9]
        int[][][] dp = new int[10][9][step + 1];
        dp[a][b][0] = 1;
        for (int k = 0; k < step + 1; k++) {
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 9; j++) {
                    if (k == 0) {
                        if (i == a && j == b) {
                            dp[i][j][k] = 1;
                        } else {
                            dp[i][j][k] = -1;
                        }
                    } else {
                        int p1 = (i - 2 >= 0 && j + 1 < 9) ? dp[i - 2][j + 1][k - 1] : -1;
                        int p2 = (i - 1 >= 0 && j + 2 < 9) ? dp[i - 1][j + 2][k - 1] : -1;
                        int p3 = (i - 1 >= 0 && j - 2 >= 0) ? dp[i - 1][j - 2][k - 1] : -1;
                        int p4 = (i - 2 >= 0 && j - 1 >= 0) ? dp[i - 2][j - 1][k - 1] : -1;
                        int p5 = (i + 2 < 10 && j + 1 < 9) ? dp[i + 2][j + 1][k - 1] : -1;
                        int p6 = (i + 1 < 10 && j + 2 < 9) ? dp[i + 1][j + 2][k - 1] : -1;
                        int p7 = (i + 1 < 10 && j - 2 >= 0) ? dp[i + 1][j - 2][k - 1] : -1;
                        int p8 = (i + 2 < 10 && j - 1 >= 0) ? dp[i + 2][j - 1][k - 1] : -1;
                        dp[i][j][k] = (p1 == -1 ? 0 : p1) + (p2 == -1 ? 0 : p2) + (p3 == -1 ? 0 : p3) + (p4 == -1 ? 0 : p4) + (p5 == -1 ? 0 : p5) + (p6 == -1 ? 0 : p6) + (p7 == -1 ? 0 : p7) + (p8 == -1 ? 0 : p8);
                    }
                }
            }
        }
        return dp[0][0][step];
    }

}

演演算法和資料結構筆記

象棋中的馬跳步問題

象棋中的馬跳步問題

題目描述

暴力解法

動態規劃解（可 AC）

更多