Chess Knight Minimo si sposta a destinazione su una tavola infinita
-
05-11-2019 - |
Domanda
Ci sono toni di soluzioni per Knights Tour o percorso più breve per i cavalieri dal movimento della cellula di origine a cella di destinazione. La maggior parte delle soluzioni utilizza BFS che sembra il miglior algoritmo.
Ecco la mia implementazione usando Hashmap:
public class Knight_HashMap {
static HashMap<String, Position> chessboard = new HashMap<String, Position>();
static Queue<Position> q = new LinkedList<Position>();
static int Nx, Ny, Kx, Ky, Cx, Cy;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("insert Board dimentions: Nx, Ny");
Nx = sc.nextInt();
Ny = sc.nextInt();
System.out.println("inset Knight's location: Kx, Ky");
Kx = sc.nextInt();
Ky = sc.nextInt();
System.out.println("insert destination location: Cx, Cy");
Cx = sc.nextInt();
Cy = sc.nextInt();
sc.close();
// Assume the position for simplicity. In real world, accept the values using
// Scanner.
Position start = new Position(Kx, Ky, 0); // Positionition 0, 1 on the chessboard
Position end = new Position(Cx, Cy, Integer.MAX_VALUE);
chessboard.put(Arrays.toString(new int[] { Kx, Ky }), new Position(Kx, Ky, 0));
q.add(start);
while (q.size() != 0) // While queue is not empty
{
Position pos = q.poll();
if (end.equals(pos)) {
System.out.println("Minimum jumps required: " + pos.depth);
return;
} else {
// perform BFS on this Position if it is not already visited
bfs(pos, ++pos.depth);
}
}
}
private static void bfs(Position current, int depth) {
// Start from -2 to +2 range and start marking each location on the board
for (int i = -2; i <= 2; i++) {
for (int j = -2; j <= 2; j++) {
Position next = new Position(current.x + i, current.y + j, depth);
if (isValid(current, next)) {
if (inRange(next.x, next.y)) {
// chessboard.put(Arrays.toString(new int[] { next.x, next.y }), next);
// Skip if next location is same as the location you came from in previous run
if (current.equals(next))
continue;
Position position = chessboard.get(Arrays.toString(new int[] { next.x, next.y }));
if (position == null) {
position = new Position(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);
}
/*
* Get the current position object at this location on chessboard. If this
* location was reachable with a costlier depth, this iteration has given a
* shorter way to reach
*/
if (position.depth > depth) {
chessboard.put(Arrays.toString(new int[] { current.x + i, current.y + j }),
new Position(current.x, current.y, depth));
// chessboard.get(current.x + i).set(current.y + j, new Position(current.x,
// current.y, depth));
q.add(next);
}
}
}
}
}
}
private static boolean isValid(Position current, Position next) {
// Use Pythagoras theorem to ensure that a move makes a right-angled triangle
// with sides of 1 and 2. 1-squared + 2-squared is 5.
int deltaR = next.x - current.x;
int deltaC = next.y - current.y;
return 5 == deltaR * deltaR + deltaC * deltaC;
}
private static boolean inRange(int x, int y) {
return 0 <= x && x < Nx && 0 <= y && y < Ny;
}
}
class Position {
public int x;
public int y;
public int depth;
Position(int x, int y, int depth) {
this.x = x;
this.y = y;
this.depth = depth;
}
public boolean equals(Position that) {
return this.x == that.x && this.y == that.y;
}
public String toString() {
return "(" + this.x + " " + this.y + " " + this.depth + ")";
}
}
Funziona bene con una piccola dimensione ma con 10^9 x 10^9 I faccia outOfMemory
eccezione. Ho anche provato con Java 2D Array, ArrayList, HashMap insieme a una lista Linked come coda. Ma per quella dimensione 10^9 x 10^9 con qualsiasi struttura di dati, ho affrontato outOfMemory
eccezione.
C'è possibilità di ottimizzazione da evitare outOfMemory
O qualche altro modo/struttura dati per gestire una dimensione così enorme?
Nota: Dovrei menzionare che questa domanda proviene da Contest BAPC17 di nome Knight's Marathon
Nessuna soluzione corretta