1197. Minimum Knight Moves

bfs
有数学方法 不实际

class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x), y = abs(y);
        unordered_map<int, int> m{{0, 0}};
        int dx[] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        using tdii = tuple<double, int, int>;
        priority_queue<tdii, vector<tdii>, greater<tdii>> q;
        q.emplace(0, 0, 0);
        while (!q.empty()) {
            auto [_, xx, yy] = q.top(); q.pop();
            if (xx == x && yy == y) return m[x * 1000 + y];
            for (int i = 0; i < 8; ++i) {
                int nx = xx + dx[i], ny = yy + dy[i], k = nx * 1000 + ny;
                if (nx < -1 || ny < -1 || abs(nx) + abs(ny) > 300 || m.count(k)) continue;
                m[k] = m[xx * 1000 + yy] + 1;
                q.emplace(m[k] + dist(nx, ny, x, y), nx, ny);
            }
        }
        return 0;
    }

    double dist(int xx, int yy, int x, int y) {
        return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
    }
};

用这个

// hashmap for pair
auto cmp = [](const auto &a) { return hash<long>{}(a.first) ^ hash<long>{}((long)a.second << 32); };
unordered_map<pair<int, int>, std::vector<pair<int, int>>, decltype(cmp)> m(101, cmp);

class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x), y = abs(y); // 所有坐标调整为第一象限quadrant
        unordered_set<int> s{0};
        int res = 0, dx[] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        queue<pair<int, int>> q{{{0, 0}}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto [xx, yy] = q.front(); q.pop();
                if (xx == x && yy == y) return res;
                for (int j = 0; j < 8; ++j) {
                    int nx = xx + dx[j], ny = yy + dy[j], k = nx * 1000 + ny; // 这里乘1000因为x和y的绝对值都不超过300
                    if (nx < -1 || ny < -1 || abs(nx) + abs(ny) > 300 || s.count(k)) continue; // 这里检查nx和ny是否小于-1是因为到(1, 1)最少步数必须跨象限先到(2, -1)或者(-1, 2)，其他所有走法都比这个差，实际上从0开始跨象限最多到-1到不了-2即从1到-1因为走日字步长最多为2
                    q.emplace(nx, ny);
                    s.insert(k);
                }
            }
            ++res;
        }
        return res;
    }
};

class Solution {
public:
    int minKnightMoves(int x, int y) {
        int t = abs(x) * 1000 + abs(y);
        unordered_set<int> s{0};
        int res = 0, dx[] = {1000, 2000, 2000, 1000, -1000, -2000, -2000, -1000}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
        queue<int> q{{0}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int u = q.front(); q.pop();
                if (u == t) return res;
                for (int j = 0; j < 8; ++j) {
                    int v = u + dx[j] + dy[j];
                    if (v < 0 || s.count(v)) continue;
                    q.emplace(v);
                    s.insert(v);
                }
            }
            ++res;
        }
        return res;
    }
};