Gente estou intrigado agora, o site do UVA, eles não me respondem o suporte, então vou ter que recorrer até voces.
O seguinte problema do UVA:
Knight Moves
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=380
Explicação do problema:
Ele te da dois pontos no tabuleiro de xadrez, voce tem que calcular a quantidade minima de movimentos entre um ponto e outro com o cavalo ( anda em L ).
Mas nos testes que ele da passa em todos, e eu fiz um esquema aqui de BITMASK que calcula todas as possibilidades de um ponto até o outro, nem um deles deu Runtime error.
Mas quando dou submit no UVA, da Runtime error, não entendo o porque.
Será que alguem consegue enchergar onde esta o erro ?
Codigo:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
private int[] dkX = { 1, -1, 1, -1, 2, 2, -2, -2 };
private int[] dkY = { 2, 2, -2, -2, 1, -1, 1, -1 };
private boolean[][] flags;
private int[][] dist;
public void bfs(int sx, int sy, int ex, int ey) {
Queue<Integer[]> q = new LinkedList<Integer[]>();
q.add(new Integer[] { sx, sy });
flags[sx][sy] = true;
while (!q.isEmpty()) {
Integer[] aux = q.poll();
if (aux[0] == ex && aux[1] == ey)
break;
for (int i = 0; i < 8; i++) {
int bx = dkX[i] + aux[0];
int by = dkY[i] + aux[1];
if (isValid(bx, by) && !flags[bx][by]) {
dist[bx][by] = dist[aux[0]][aux[1]] + 1;
q.offer(new Integer[] { bx, by });
flags[bx][by] = true;
}
}
}
}
public int[] index(String place) {
int row = 8 - (place.charAt(1) - '0');
int col = (place.charAt(0) - 'a');
return new int[] { row, col };
}
public void solve() {
Scanner sc = new Scanner(System.in);
while (true) {
String[] ab = sc.nextLine().split("\\s");
if (ab.length <= 1) {
break;
}
int[] start = index(ab[0]);
int[] end = index(ab[1]);
flags = new boolean[8][8];
dist = new int[8][8];
bfs(start[0], start[1], end[0], end[1]);
System.out.println("To get from " + ab[0] + " to " + ab[1] + " takes " + dist[end[0]][end[1]] + " knight moves.");
}
}
public boolean isValid(int x, int y) {
return x >= 0 && y >= 0 && x < 8 && y < 8;
}
public static void main(String[] args) {
new Main().solve();
System.exit(0);
}
}
