獲得n * m棋盤上棋子的最短路徑

Question

我一直在解決一個任務，需要我計算從一個點到另一個棋子在B點上所需的最小步數有障礙，並輸出所採取的路徑。

我一直在尋找在A *算法，但它需要我得到一個很好的啓發估計，我不知道如何獲得一個棋子像騎士

我一直在努力做的是首先使用廣度優先搜索找到的從A點到達B點沒有障礙所需的步驟最少的號碼，然後使用A *算法

public void AllPaths(int[,] chessBoard, int startX, int startY, int dimension) { 
    // All the moves a knight can make 
    int[] movementX = new int[8]{-2, -2, -1, -1, 1, 1, 2, 2}; 
    int[] movementY = new int[8]{-1, 1, -2, 2, -2, 2, -1, 1}; 
    chessBoard[startX, startY] = 0; 

    for (int step = 0; step < dimension-1; step++) { 
    for (int x = 0; x < dimension; x++) { 
     for (int j = 0; j < dimension; j++) { 
     if (chessBoard[x, j] == step) { 
      for (int k = 0; k < 8; k++) { 
      if (movementY[k] + x>= 0 && movementY[k] + x < dimension && movementX[k] + j >= 0 && movementX[k]+j < dimension) { 
       if (chessBoard[movementY[k]+x,movementX[k]+j] == -1) { 
       chessBoard[movementY[k]+x,movementX[k]+j] = step + 1; 
       } 
      } 
      } 
     } 
     } 
    } 
    } 
} 

爲騎士的移動輸入和輸出如下：

-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

- starting from the top left 
0 3 2 3 2 3 4 5 
3 4 1 2 3 4 3 4 
2 1 4 3 2 3 4 5 
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5 
3 4 3 4 3 4 5 4 
4 3 4 3 4 5 4 5 
5 4 5 4 5 4 5 6 

這適用於n * n個電路板，但我也需要它爲n * m電路板工作。 我正朝着正確的方向走還是應該完全使用其他東西？ 我必須改變它爲n * m電路板工作嗎？ 感謝您提出任何關於解決我遇到的問題的建議。

Answer 1

您需要兩個參數來描述n * m板。

而是循環的步理論最大數量的，只是循環，直到你填補了板：

public void AllPaths(int[,] chessBoard, int startX, int startY, int dimensionX, int dimensionY) { 
    // All the moves a knight can make 
    int[] movementY = { -2, -2, -1, -1, 1, 1, 2, 2 }; 
    int[] movementX = { -1, 1, -2, 2, -2, 2, -1, 1 }; 
    chessBoard[startX, startY] = 0; 
    int cnt = dimensionX * dimensionY - 1: 
    int step = 0; 

    while (cnt > 0) { 
    for (int x = 0; x < dimension; x++) { 
     for (int y = 0; y < dimension; y++) { 
     if (chessBoard[x, y] == step) { 
      for (int k = 0; k < 8; k++) { 
      int dx = movementX[k] + x, dy = movementY[k] + y; 
      if (dx >= 0 && dx < dimensionX && dy >= 0 && dy < dimensionY) { 
       if (chessBoard[dx, dy] == -1) { 
       chessBoard[dx, dy] = step + 1; 
       cnt--; 
       } 
      } 
      } 
     } 
     } 
    } 
    step++; 
    } 
}