1197. Minimum Knight Moves

https://leetcode.com/problems/minimum-knight-moves/

无限国际象棋棋盘上从任意点当做原点，问走马步到(x, y)至少需要多少步。图上最少步数=>BFS。观察可知走的方式是对称的，因此(x, y)可以取绝对值放到第一象限并把BFS限制在第一象限探索，除了前面两步可能会牵扯跨象限再跨回来。除此之外还有O(1)的数学解。

class Solution {
public:
    int minKnightMoves(int x, int y) {
        if (x == 0 && y == 0) return 0;
        vector<vector<int>> dirs{{2, 1}, {1, 2}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {-2, -1}, {-1, -2}};
        x = abs(x);
        y = abs(y);
        vector<vector<bool>> visited(304, vector<bool>(304, false));
        visited[0][0] = true;
        queue<pair<int, int>> q;
        q.push({0, 0});
        int cnt = 0;
        while (!q.empty()) {
            ++cnt;
            for (int i = q.size() - 1; i >= 0; --i) {
                const auto t = q.front(); q.pop();
                for (const auto &dir : dirs) {
                    int i = t.first + dir[0], j = t.second + dir[1];
                    if (i == x && j == y) return cnt;
                    if (i >= -3 && i < 301 && j >= -3 && j < 301 && !visited[i + 3][j + 3]) {
                        q.push({i, j});
                        visited[i + 3][j + 3] = true;
                    }
                }
            }
        }
        return -1;
    }
};