题目:5073. 进击的骑士
一个坐标可以从 -infinity
延伸到 +infinity
的 无限大的 棋盘上,你的 骑士 驻扎在坐标为 [0, 0]
的方格里。
骑士的走法和中国象棋中的马相似,走 “日” 字:即先向左(或右)走 1 格,再向上(或下)走 2 格;或先向左(或右)走 2 格,再向上(或下)走 1 格。
每次移动,他都可以按图示八个方向之一前进。
现在,骑士需要前去征服坐标为 [x, y] 的部落,请你为他规划路线。
最后返回所需的最小移动次数即可。本题确保答案是一定存在的。
示例 1:
输入:x = 2, y = 1
输出:1
解释:[0, 0] → [2, 1]
示例 2:
输入:x = 5, y = 5
输出:4
解释:[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
提示:
|x| + |y| <= 300
题解:
比较愚笨的办法就是用 宽度优先搜索(BFS) 算法走到目标点为止。我采用的也是这种算法。至于第一名的用的算法在下实在是看不懂,姑且先放着。我在CSDN论坛发的讨论第一名写的代码的帖子。
很明显,棋盘是对称的。直接将目标点坐标取绝对值,调整到第一象限或 X
轴或 Y
轴。
然后只在第一象限用BFS算得结果。
起点(0,0)是特殊点,直接返回 0。
点(1,1)也是特殊点,因为只在第一象限的话到达(1,1)至少要 4 步,但是如果可以通过其他象限的话,只需要 2 步即可到达(1,1)。
用二维数组 board[x + 3][y + 3]
表示到达点(r,c)的最少步数。
到达一个点后,如果合法,则步数等于上一个点的步数加 1。如果是目标点,直接返回步数,否则将坐标入队列。
时间复杂度: 在下无能为力
空间复杂度: 在下还是无能为力
Java:
class Solution {
public int minKnightMoves( int x,
int y) {
x = Math.abs(x);// 调整到第一象限
y = Math.abs(y);
if (x + y == 0) {// 起点(0,0)
return 0;
}
if (x == 1 && y == 1) {// 此算法是无法计算点(1,1)的最少步数
return 2;
}
int m = x + 3;
int n = y + 3;
int[][] board = new int[m][n];
int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2 };
int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { 0, 0 });
while (!queue.isEmpty()) {
int[] cur = queue.poll();// 出队列
for (int i = 0; i < 8; ++i) {
int r = cur[0] + dx[i];
int c = cur[1] + dy[i];
if (r < 0 || r >= m || c < 0 || c >= n) {// 越界
continue;
}
if (r + c == 0) {// 回到了起点
continue;
}
if (board[r][c] == 0) {// 未访问过当前点
board[r][c] = board[cur[0]][cur[1]] + 1;
if (r == x && c == y) {// 当前点就是目标点
return board[r][c];// 返回结果
}
queue.add(new int[] { r, c });// 不是目标点,入队列
}
}
}
return -1;
}
}