java nn方格 绕过障碍物_【Java数据结构马踏棋盘问题】将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中...
展开全部
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import java.util.Stack;
public class T {
private static final int[][] MOVES = new int[][] { { -2, 1 }, { -1, 2 },
{ 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 } };
private static final int SIZE = 8;
private static final int BASE = SIZE + 4;
private static int[][] board;
private static NeighborComparator neighborComparator = new NeighborComparator();
public static void main(String[] args) {
board = new int[BASE][BASE];
for (int r = 0; r
for (int c = 0; c
if (r BASE - 3 || c BASE - 3) {
board[r][c] = -1;
}
}
}
int row = 2 + new Random().nextInt(SIZE);
int col = 2 + new Random().nextInt(SIZE);
solve(row, col);
}
private static void solve(int r, int c) {
Stack stack = new Stack();
int count = 1;
Cell cell = new Cell(r, c, neighbors(r, c));
stack.push(cell);
board[r][c] = count++;
while (!stack.isEmpty()) {
if (stack.size() == SIZE * SIZE) {
break;
}
cell = stack.peek();
if (cell.nextNeighbor
int[] neighbor = cell.neighbors.get(cell.nextNeighbor);
r = neighbor[0];
c = neighbor[1];
board[r][c] = count++;
stack.push(new Cell(r, c, neighbors(r, c)));
cell.nextNeighbor++;
} else {
stack.pop();
board[cell.r][cell.c] = 0;
count--;
}
}
if (stack.size() == SIZE * SIZE) {
print();
} else {
System.out.println("无解");
}
}
private static class NeighborComparator implements Comparator {
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
}
private static List neighbors(int r, int c) {
List neighbors = new ArrayList<>();
for (int[] m : MOVES) {
int x = m[0];
int y = m[1];
if (board[r + y][c + x] == 0) {
neighbors.add(new int[] { r + y, c + x, countNeighbors(r + y, c + x) });
}
}
Collections.sort(neighbors, neighborComparator);
return neighbors;
}
private static int countNeighbors(int r, int c) {
int num = 0;
for (int[] m : MOVES) {
if (board[r + m[1]][c + m[0]] == 0) {
num++;
}
}
return num;
}
private static void print() {
for (int i = 2; i
for (int j = 2; j
System.out.printf("%2d ", board[i][j]);
}
System.out.println();
}
System.out.println();
}
private static class Cell {
int r;
int c;
List neighbors;
int nextNeighbor = 0;
public Cell(int r, int c, List neighbors) {
this.r = r;
this.c = c;
this.neighbors = neighbors;
}
}
}