我需要關于這個問題的建議,稱為“騎士之路”。給定一個 n*n 棋盤,其單元格初始化為 0,我需要確定,給定任意騎士的位置,如果騎士可以通過棋盤上的每個單元格恰好一次,騎士訪問過的每個單元格都將被標記為計數器,從:1 - n^2 開始計數。如果路徑可行,我需要列印電路板。我需要列印所有有效的板。對于不懂棋規的人來說,馬可以垂直上下一格,水平兩格,或者垂直上下兩格,水平一格。
例如,給定一個 5*5 的板,從 (0,0) 開始,該方法應列印:
{{1,16,11,6,21},
{10,5,20,15,12},
{17,2,13,22,7},
{4,9,24,19,14},
{25,18,3,8,23}};
上述輸出將是少數幾個之一,因為考慮不同的初始位置可能有不同的其他方式。我寫了下面的代碼,但它沒有列印任何東西。我需要發現這里的邏輯缺陷,這樣我才能讓它發揮作用。
public class KnightDemo {
static int counter = 1;
public static void KnightPath(int[][] b, int i, int j) {
b[i][j] = counter;
if (counter == b.length * b[0].length) {
printMatrix(b);
return;
} else {
counter ;
if (isValid(b, i - 1, j 2) && b[i - 1][j 2] == 0) {
KnightPath(b, i - 1, j 2);
} else {
return;
}
if (isValid(b, i - 2, j 1) && b[i - 1][j 1] == 0) {
KnightPath(b, i - 2, j 1);
} else {
return;
}
if (isValid(b, i - 1, j - 2) && b[i - 1][j - 2] == 0) {
KnightPath(b, i - 1, j - 2);
} else {
return;
}
if (isValid(b, i - 2, j - 1) && b[i - 2][j - 1] == 0) {
KnightPath(b, i - 2, j - 1);
} else {
return;
}
if (isValid(b, i 2, j - 1) && b[i 2][j - 1] == 0) {
KnightPath(b, i 2, j - 1);
} else {
return;
}
if (isValid(b, i 1, j - 2) && b[i 1][j - 2] == 0) {
KnightPath(b, i 1, j - 2);
} else {
return;
}
if (isValid(b, i 1, j 2) && b[i 1][j 2] == 0) {
KnightPath(b, i 1, j 2);
} else {
return;
}
if (isValid(b, i 2, j 1) && b[i 2][j 1] == 0) {
KnightPath(b, i 2, j 1);
} else {
return;
}
}
}
public static boolean isValid(int[][] a, int i, int j) {
if (i > a.length - 1 || i < 0 || j > a[0].length - 1 || j < 0) {
return false;
}
return true;
}
public static void main(String[] args) {
int[][] b = new int[5][5];
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < b[0].length; j ) {
KnightPath(b, i, j);
}
}
}
public static void printMatrix(int[][] matrix) {
for (int[] rows: matrix) {
StringBuilder buff = new StringBuilder();
buff.append("[");
for (int i = 0; i < rows.length; i ) {
int value = rows[i];
buff.append(value);
if (i < rows.length - 1) {
buff.append(", ");
}
}
buff.append("]");
System.out.println(buff.toString());
}
}
}
輸出是
[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]
[21, 22, 23, 24, 25]
uj5u.com熱心網友回復:
根據評論部分中OP的解釋,目標是繪制出騎士可以從棋盤上的某個位置采取的所有可能路徑。基本上,給定騎士的位置b[i][j],計算所有合法路徑。
如果馬位于 {0, 0},則馬只有兩條合法路徑,分別以 {1, 2} 和?? {2, 1} 結尾。這里的想法是在地圖中捕獲它。然后,移動到板上的下一個位置(即{1, 0})并重復該程序。由于可以將每個棋盤位置標識為整數 ( counter),我們可以使用它來映射路徑...
0=[{1, 2}, {2, 1}]
1=[{2, 2}, {1, 3}, {2, 0}]
...
n=[{n^-2 - 3, n^-2 - 2}, {n^-2 - 2, n^-2 - 3}] // last location is always a corner
為了簡單起見,我決定創建一個record坐標 Java 來存盤給定路徑的結束位置的{ x, y } 坐標,制作我的地圖<Integer, Set<Coordinates>>
這里的邏輯很簡單。首先,使用矩陣中每個對應位置的空串列為地圖播種。然后,遍歷矩陣(二維陣列)并計算騎士可以從這個位置走的所有合法路徑。對于每個合法路徑,添加路徑Coordinates的結束位置。我用 aSet來消除重復的坐標。
我的解決方案(可能不是最佳的)如下(使用 OP 代碼作為基線) - 需要 Java 15 或更高版本才能運行。對于 Java 14 或更早版本,替換Coordinates為Integer[]長度為 2 的 a,并將坐標存盤在其中。
public class KnightDemo {
static int counter = 0;
static Map<Integer, Set<Coordinates>> map = new HashMap<>();
public static void KnightPath(int[][] b, int i, int j) {
Set<Coordinates> paths = map.get(counter);
if (isValid(b, i - 1, j 2)) {
paths.add(new Coordinates(i - 1, j 2));
map.put(counter, paths);
}
if (isValid(b, i - 2, j 1)) {
paths.add(new Coordinates(i - 2, j 1));
map.put(counter, paths);
}
if (isValid(b, i - 1, j - 2)) {
paths.add(new Coordinates(i - 1, j - 2));
map.put(counter, paths);
}
if (isValid(b, i - 2, j - 1)) {
paths.add(new Coordinates(i - 2, j - 1));
map.put(counter, paths);
}
if (isValid(b, i 2, j - 1)) {
paths.add(new Coordinates(i 2, j - 1));
map.put(counter, paths);
}
if (isValid(b, i 1, j - 2)) {
paths.add(new Coordinates(i 1, j - 2));
map.put(counter, paths);
}
if (isValid(b, i 1, j 2)) {
paths.add(new Coordinates(i 1, j 2));
map.put(counter, paths);
}
if (isValid(b, i 2, j 1)) {
paths.add(new Coordinates(i 2, j 1));
map.put(counter, paths);
}
counter ;
}
public static boolean isValid(int[][] a, int i, int j) {
return i >= 0 && i < a.length && j >= 0 && j < a[0].length;
}
public static void main(String[] args) {
int[][] b = new int[5][5];
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < b[0].length; j ) {
map.put(counter, new HashSet<>()); // add a new set before calculating paths
KnightPath(b, i, j);
}
}
map.entrySet().stream().forEach(System.out::println);
}
private static record Coordinates(int row, int col) {
@Override
public String toString() {
return "{" row ", " col "}";
}
}
}
程式輸出:
0=[{1, 2}, {2, 1}]
1=[{2, 2}, {1, 3}, {2, 0}]
2=[{2, 3}, {1, 4}, {2, 1}, {1, 0}]
3=[{2, 2}, {1, 1}, {2, 4}]
4=[{2, 3}, {1, 2}]
5=[{2, 2}, {0, 2}, {3, 1}]
6=[{2, 3}, {0, 3}, {3, 0}, {3, 2}]
7=[{0, 0}, {3, 3}, {2, 4}, {0, 4}, {3, 1}, {2, 0}]
8=[{0, 1}, {3, 4}, {3, 2}, {2, 1}]
9=[{3, 3}, {2, 2}, {0, 2}]
10=[{1, 2}, {0, 1}, {4, 1}, {3, 2}]
11=[{0, 0}, {3, 3}, {1, 3}, {0, 2}, {4, 0}, {4, 2}]
12=[{0, 1}, {3, 4}, {1, 4}, {0, 3}, {4, 1}, {3, 0}, {1, 0}, {4, 3}]
13=[{1, 1}, {4, 4}, {0, 2}, {0, 4}, {4, 2}, {3, 1}]
14=[{1, 2}, {0, 3}, {4, 3}, {3, 2}]
15=[{2, 2}, {1, 1}, {4, 2}]
16=[{2, 3}, {1, 2}, {1, 0}, {4, 3}]
17=[{1, 1}, {4, 4}, {2, 4}, {1, 3}, {4, 0}, {2, 0}]
18=[{1, 2}, {1, 4}, {4, 1}, {2, 1}]
19=[{2, 2}, {1, 3}, {4, 2}]
20=[{3, 2}, {2, 1}]
21=[{3, 3}, {2, 2}, {2, 0}]
22=[{3, 4}, {2, 3}, {3, 0}, {2, 1}]
23=[{2, 2}, {2, 4}, {3, 1}]
24=[{2, 3}, {3, 2}]
更新:你能在真正的國際象棋游戲中使用它嗎?
是的你可以!black假設您使用和為矩陣播種white。您可以增強邏輯,這樣,如果結束位置與您的顏色相對應,您就不會添加為有效路徑,因為它被您的一件作品擋住了。
第二次更新:相同的代碼,但使用Coordinate物件作為鍵
public class KnightDemo {
static int counter = 0;
static Map<Coordinates, Set<Coordinates>> map = new HashMap<>();
public static void KnightPath(int[][] b, Coordinates coordinates) {
Set<Coordinates> paths = map.get(coordinates);
if (isValid(b, coordinates.row() - 1, coordinates.col() 2)) {
paths.add(new Coordinates(coordinates.row() - 1, coordinates.col() 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() - 2, coordinates.col() 1)) {
paths.add(new Coordinates(coordinates.row() - 2, coordinates.col() 1));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() - 1, coordinates.col() - 2)) {
paths.add(new Coordinates(coordinates.row() - 1, coordinates.col() - 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() - 2, coordinates.col() - 1)) {
paths.add(new Coordinates(coordinates.row() - 2, coordinates.col() - 1));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 2, coordinates.col() - 1)) {
paths.add(new Coordinates(coordinates.row() 2, coordinates.col() - 1));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 1, coordinates.col() - 2)) {
paths.add(new Coordinates(coordinates.row() 1, coordinates.col() - 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 1, coordinates.col() 2)) {
paths.add(new Coordinates(coordinates.row() 1, coordinates.col() 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 2, coordinates.col() 1)) {
paths.add(new Coordinates(coordinates.row() 2, coordinates.col() 1));
map.put(coordinates, paths);
}
}
public static boolean isValid(int[][] a, int i, int j) {
return i >= 0 && i < a.length && j >= 0 && j < a[0].length;
}
public static void main(String[] args) {
int[][] b = new int[5][5];
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < b[0].length; j ) {
Coordinates coordinates = new Coordinates(i, j);
map.put(coordinates, new HashSet<>());
KnightPath(b, coordinates);
counter ;
}
}
map.entrySet().stream().forEach(System.out::println);
}
private static record Coordinates(int row, int col) {
@Override
public String toString() {
return "{" row ", " col "}";
}
}
}
輸出:
{0, 0}=[{1, 2}, {2, 1}]
{2, 2}=[{0, 1}, {3, 4}, {1, 4}, {0, 3}, {4, 1}, {3, 0}, {1, 0}, {4, 3}]
{4, 4}=[{2, 3}, {3, 2}]
{0, 1}=[{2, 2}, {1, 3}, {2, 0}]
{2, 3}=[{1, 1}, {4, 4}, {0, 2}, {0, 4}, {4, 2}, {3, 1}]
{0, 2}=[{2, 3}, {1, 4}, {2, 1}, {1, 0}]
{2, 4}=[{1, 2}, {0, 3}, {4, 3}, {3, 2}]
{0, 3}=[{2, 2}, {1, 1}, {2, 4}]
{0, 4}=[{2, 3}, {1, 2}]
{3, 0}=[{2, 2}, {1, 1}, {4, 2}]
{3, 1}=[{2, 3}, {1, 2}, {1, 0}, {4, 3}]
{1, 0}=[{2, 2}, {0, 2}, {3, 1}]
{3, 2}=[{1, 1}, {4, 4}, {2, 4}, {1, 3}, {4, 0}, {2, 0}]
{1, 1}=[{2, 3}, {0, 3}, {3, 0}, {3, 2}]
{3, 3}=[{1, 2}, {1, 4}, {4, 1}, {2, 1}]
{1, 2}=[{0, 0}, {3, 3}, {2, 4}, {0, 4}, {3, 1}, {2, 0}]
{3, 4}=[{2, 2}, {1, 3}, {4, 2}]
{1, 3}=[{0, 1}, {3, 4}, {3, 2}, {2, 1}]
{1, 4}=[{3, 3}, {2, 2}, {0, 2}]
{4, 0}=[{3, 2}, {2, 1}]
{4, 1}=[{3, 3}, {2, 2}, {2, 0}]
{2, 0}=[{1, 2}, {0, 1}, {4, 1}, {3, 2}]
{4, 2}=[{3, 4}, {2, 3}, {3, 0}, {2, 1}]
{2, 1}=[{0, 0}, {3, 3}, {1, 3}, {0, 2}, {4, 0}, {4, 2}]
{4, 3}=[{2, 2}, {2, 4}, {3, 1}]
它們的列印順序不同,但您可以看出坐標與前面示例中的{2, 2}設定相同。counter==12單元格 {2, 2} 是左上角的第 13 個單元格。
uj5u.com熱心網友回復:
要解決所有路徑,您需要重置已用盡的路徑的放置值,以便更新的路徑可以訪問它們。此外,您的計數器應該反映您已經走了多深,因此如果您退出嘗試另一條路徑,您的計數器也應該回滾。我建議將計數器作為引數傳遞,而不是使用靜態計數器。此外,如果您想嘗試所有有效的可能性,那么只要一種可能性被認為無效,您就需要避免使用這些 return 陳述句。
public static void KnightPath(int[][] b, int i, int j, int counter) {
...
if (isValid(b, i - 1, j 2) && b[i - 1][j 2] == 0) {
KnightPath(b, i - 1, j 2, counter 1);
}
...
b[i][j] = 0;
}
public static void main(String[] args) {
...
KnightPath(b, i, j, 1);
...
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qiye/426862.html
上一篇:如何在JMeter中實作遞回?
下一篇:獲取父母所有后代的快速方法
