GuilinDev
Lc1197
05 August 2008
1197 Minimum Knight Moves
题目
In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].
A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.
Example 1:
1
2
3
Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]
Example 2:
1
2
3
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
Constraints:
1
|x| + |y| <= 300
分析
如果用DFS枚举所有走法，然后挑出一个最小的路径，会爆栈。
其实题目的坐标是-x -y | -x y | x -y | x y | 四个象限 互为镜像的，也就是 可以只考虑 x y的情况即可，让x = |x|, y = |y|，使用bfs 宽度优先搜索，搜索中检查是否被访问过和是否在该层边界内，也就是求最短路径的问题。
时间复杂度：O(V+E)，V是访问的节点个数，E是边。
空间复杂度：O(V)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public int minKnightMoves(int x, int y) {
// 八个方向
int[][] dirs = { {-2,1},{-1,2},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2} };
// 小优化，也可不用
x = Math.abs(x);
y = Math.abs(y)
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
HashSet<String> visited = new HashSet();
int steps = 0;
visited.add("0,0"); // 将坐标转换成string，方便查找
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curPos = queue.poll();
if (curPos[0] == x && curPos[1] == y) {
return steps;
}
for (int[] dir : dirs) {
int newX = curPos[0] + dir[0];
int newY = curPos[1] + dir[1];
String newPos = newX + "," + newY;
if (!visited.contains(newPos)) {
queue.offer(new int[]{newX, newY});
visited.add(newPos);
}
}
}
steps++;
}
return -1;
}
}