_1197.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.Queue;
importjava.util.Set;

publicclass_1197 {
publicstaticclassSolution1 {
/*
 * My completely original solution.
 */
publicintminKnightMoves(intx, inty) {
intboundary = 600; // this is from the constraints of this problem: -300 <= x, y <= 300
Queue<int[]> q = newLinkedList<>();
q.offer(newint[] {0, 0});
intmoves = 0;
int[][] dirs =
newint[][] {
 {-2, 1},
 {-1, 2},
 {1, 2},
 {2, 1},
 {2, -1},
 {1, -2},
 {-1, -2},
 {-2, -1}
 };
Set<Integer> visited = newHashSet<>();
visited.add(0);
while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
int[] curr = q.poll();
if (curr[0] == x && curr[1] == y) {
returnmoves;
 }
for (int[] dir : dirs) {
intnextx = dir[0] + curr[0];
intnexty = dir[1] + curr[1];
if (visited.add(nexty * boundary + nextx)) {
// formula: col * size of matrix + row, is a common way to project a 2D
// matrix onto 1D array
q.offer(newint[] {nextx, nexty});
 }
 }
 }
moves++;
 }
returnmoves;
 }
 }
}