在与谷歌进行的45分钟技术面试中，我遇到了一个Leaper Graph问题。 我编写了可以工作的代码，但后来被拒绝了工作机会，因为我缺乏数据结构知识。 我在想我还能做得更好点什么。
问题是这样的：给定一个大小为N的棋盘，并告诉你一件棋子可以水平跳跃i个位置（左或右），并且垂直跳跃j个位置（上或下）（即，类似于国际象棋中的马），那么跳跃者能否到达棋盘上的每个位置？
我编写了以下算法。 它通过递归地查找是否可以到达棋盘上的每个位置来标记访问过的图上的所有点。 如果无法到达，则至少有一个字段为false，函数将返回false。
现在，有人指出最佳解决方案是实现唐纳德·克努斯的互质实现：http://arxiv.org/pdf/math/9411240v1.pdf。45分钟的技术面试中是否应该能够找到这个答案呢？
除了上述内容，我还能做得更好吗？
编辑： - 我询问了起始位置。我被告知从0,0开始是可以的。
编辑2： 根据反馈，我使用了while循环和队列的方法。当n = 85时，递归方法会导致堆栈溢出。然而，下面的while循环和队列方法可以处理高达n = 30,000的问题。（此后，它将遇到内存超过GB的堆问题）。如果您知道如何进一步优化，请告诉我。
问题是这样的：给定一个大小为N的棋盘，并告诉你一件棋子可以水平跳跃i个位置（左或右），并且垂直跳跃j个位置（上或下）（即，类似于国际象棋中的马），那么跳跃者能否到达棋盘上的每个位置？
我编写了以下算法。 它通过递归地查找是否可以到达棋盘上的每个位置来标记访问过的图上的所有点。 如果无法到达，则至少有一个字段为false，函数将返回false。
static boolean reachable(int i, int j, int n) {
boolean grid[][] = new boolean[n][n];
reachableHelper(0, 0, grid, i, j, n - 1);
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (!grid[x][y]) {
return false;
}
}
}
return true;
}
static void reachableHelper(int x, int y, boolean[][] grid, int i, int j, int max) {
if (x > max || y > max || x < 0 || y < 0 || grid[x][y]) {
return;
}
grid[x][y] = true;
int i2 = i;
int j2 = j;
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
reachableHelper(x + i2, y + j2, grid, i, j, max);
reachableHelper(x + j2, y + i2, grid, i, j, max);
i2 = -i2;
}
j2 = -j2;
}
}
现在，有人指出最佳解决方案是实现唐纳德·克努斯的互质实现：http://arxiv.org/pdf/math/9411240v1.pdf。45分钟的技术面试中是否应该能够找到这个答案呢？
除了上述内容，我还能做得更好吗？
编辑： - 我询问了起始位置。我被告知从0,0开始是可以的。
编辑2： 根据反馈，我使用了while循环和队列的方法。当n = 85时，递归方法会导致堆栈溢出。然而，下面的while循环和队列方法可以处理高达n = 30,000的问题。（此后，它将遇到内存超过GB的堆问题）。如果您知道如何进一步优化，请告诉我。
static boolean isReachableLoop(int i, int j, int n) {
boolean [][] grid = new boolean [n][n];
LinkedList<Point> queue = new LinkedList<Point>();
queue.add(new Point(0,0)); // starting position.
int nodesVisited = 0;
while (queue.size() != 0) {
Point pos = queue.removeFirst();
if (pos.x >= 0 && pos.y >= 0 && pos.x < n && pos.y < n) {
if (!grid[pos.x][pos.y]) {
grid[pos.x][pos.y] = true;
nodesVisited++;
int i2 = i;
int j2 = j;
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
queue.add(new Point(pos.x+i2, pos.y+j2));
queue.add(new Point(pos.x+j2, pos.y+i2));
i2 = -i2;
}
j2 = -j2;
}
}
}
}
if (nodesVisited == (n * n)) {
return true;
} else {
return false;
}
}