面试遇到的一个问题

Question

这是有限图直接用暴力深搜或者广搜都可以吧，基本是O(nm)的复杂度

Answer 1

想象从x,y走向0,0
日== (x -= 2;y--) 或者 (x--,y -=2;)画个田字格，你就明白了，就那几种情况，不需要暴力

Answer 2

写了一个队列广搜解法，因为没有样例输入输出所以也不知道对不对，但是我测试了一下比较小的数据，基本应该是正确的。public class Horse {
private static final int[][] jump = {{-2, 1}, {-2, -1}, {2, 1}, {2, -1}, 
{-1, 2}, {-1, -2}, {1, 2}, {1, -2}};

public static void main(String[] args) {
int m = 500, n = 800, x = 35, y = 109;
boolean[][] visited = new boolean[m][n];
int[][] queue = new int[m * n][3];
int h = 0, t = -1, i, j, i2, j2;

visited[0][0] = true;
while (t++ < h) {
i = queue[t][1];
j = queue[t][2];

if (i == x && j == y) {
System.out.println("Min: " + queue[t][0]);
break;
}

for (int a = 0; a < jump.length; a++) {
i2 = i + jump[a][0];
j2 = j + jump[a][1];

if (i2 >= 0 && i2 < m && j2 >= 0 && j2 < n && !visited[i2][j2]) {
h++;
visited[i2][j2] = true;
queue[h][0] = queue[t][0] + 1;
queue[h][1] = i2;
queue[h][2] = j2;
}
}
}
}

}