LeetCode 1197. 进击的骑士（BFS）

示例 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

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;
    }
};