関小君刷题记

题目大意：

进击的骑士

一个坐标可以从 -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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1197

解题思路分析：

求最短路径，标准的bfs广度优先搜索题目。本题如果没有棋盘无限大这个条件，那么完完全全是一道简单的bfs模板题型。因此考虑到棋盘范围的因素，普通的bfs肯定会超时，所以我们应该首先确定下来从起点到终点的合理范围有哪些。显而易见，如果朝着终点越来越远的方向走肯定是浪费计算时间的部分，如果简单来为棋盘来划定一下界限，起点和终点两个坐标(x1,y1), (x2,y2)围成的四边形应该是相对合理的范围。但是考虑到如果两个点在一条直线上，或者两点间的距离过近而无法完成日字跳跃的情况，我们可以将划定的棋盘范围四周分别扩大2格即可。

此外，为了方便，我们可以将起点和终点平移到正数坐标范围内。举个例子，比如：

int x = -5; // 终点x
int y = -3; // 终点y
int startX = 0; // 起点x
int starty = 0; // 起点y

先将终点移动到(0, 0)，相应的起点会被移动到(5, 3)。此外，要考虑到上面提到的扩大2格的操作，因此，终点T应该是(2, 2)，起点S则是(7, 5)。相应的棋盘范围则是(0, 0) 到(9, 7)之间的范围，即下图蓝色区域。

确定了棋盘范围之后，剩下的就是简单的常规bfs操作了。

实现代码：

public int minKnightMoves(int x, int y) {
    // 定义bfs可以走的八个方向
    int[][] directions = {{-1,-2},{1,-2},{2,-1},{2,1}
                         ,{1,2},{-1,2},{-2,1},{-2,-1}};
    int startX=0,startY=0; // 起始坐标
    if(x<0){ // 如果终点横坐标小于0
        // 起点横坐标与终点横坐标同时移动x个单位
        startX=-x;
        x=0;
    }
    if(y<0){ // 如果终点纵坐标小于0
        // 起点纵坐标与终点纵坐标同时移动y个单位
        startY=-y;
        y=0;
    }
    // 为了将棋盘范围四周分别扩大2格，将起点和终点坐标再分别平移2个单位
    startX+=2;
    startY+=2;
    x+=2;
    y+=2;
    // 棋盘的右边界为起点和终点较大x值加2
    int right=Math.max(startX,x)+2;
    // 棋盘的下边界为起点和终点较大y值加2
    int bottom=Math.max(startY,y)+2;
    // 以下是常规bfs套路代码
    Queue<int[]> q =new LinkedList<>();
    q.offer(new int[]{startX,startY});
    boolean[][] visited = new boolean[right+1][bottom+1];
    visited[startX][startY]=true;

    int res=0;
    while(q.size()>0){
        int size=q.size();
        while(size-->0){
            int[] current = q.poll();
            if(current[0]==x&&current[1]==y){
                return res;
            }
            for(int[] direction : directions){
                int nextX=current[0]+direction[0];
                int nextY=current[1]+direction[1];
                if(nextX<=right&&nextX>=0&&nextY<=bottom&&nextY>=0
                   &&!visited[nextX][nextY]){
                    visited[nextX][nextY]=true;
                    q.offer(new int[]{nextX,nextY});
                }
            }
        }
        res++;
    }
    return -1;
}

本题解法执行时间为21ms。

Runtime: 21 ms, faster than 79.04% of Java online submissions for Minimum Knight Moves.

Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Minimum Knight Moves.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1197-minimum-knight-moves-解题思路分析/