一个坐标可以从 -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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-knight-moves 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int minKnightMoves(int x, int y) {
vector<vector<int>> dir = {{2, 1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
x = abs(x), y = abs(y);//对称的,变成正的
int m = x+20, n = y+20;//放大一点
vector<vector<bool>> visited(m, vector<bool>(n,false));
x += 10, y += 10;//偏移10个单位,保证边界的上情况能够覆盖
queue<vector<int>> q;
q.push({10,10});//起点
visited[10][10] = true;
int step = 0, size, i, j, k, ni, nj;
while(!q.empty())
{
size = q.size();
while(size--)
{
i = q.front()[0];
j = q.front()[1];
if(i==x && j==y)
return step;
q.pop();
for(k = 0; k < 8; k++)
{
ni = i + dir[k][0];
nj = j + dir[k][1];
if(ni>=0 && ni<m && nj>=0 && nj<n && !visited[ni][nj])
{
q.push({ni,nj});
visited[ni][nj] = true;
}
}
}
step++;
}
return -1;
}
};
296 ms 34.4 MB