文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

一個坐標可以從 -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
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

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

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1197. 进击的骑士（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。