Solution

Method 1 – Breadth-First Search (BFS)

Intuition

The knight moves symmetrically, so we can always solve for the first quadrant and use BFS to find the shortest path. BFS explores all possible moves level by level and guarantees the minimum steps.

Approach

Take absolute values of x and y (due to symmetry).
Use BFS starting from (0,0), with a queue and a visited set.
For each position, try all 8 possible knight moves.
Stop when reaching (x, y) and return the number of steps.
Use a reasonable bound (e.g., x+3, y+3) to limit the search space.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minKnightMoves(int x, int y) {\n        x = abs(x); y = abs(y);\n        vector<pair<int,int>> dirs = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};\n        queue<pair<int,int>> q;\n        set<pair<int,int>> vis;\n        q.push({0,0});\n        vis.insert({0,0});\n        int steps = 0;\n        while (!q.empty()) {\n            int sz = q.size();\n            while (sz--) {\n                auto [cx, cy] = q.front(); q.pop();\n                if (cx == x && cy == y) return steps;\n                for (auto& d : dirs) {\n                    int nx = cx + d.first, ny = cy + d.second;\n                    if (nx >= -2 && ny >= -2 && nx <= x+2 && ny <= y+2 && !vis.count({nx,ny})) {\n                        vis.insert({nx,ny});\n                        q.push({nx,ny});\n                    }\n                }\n            }\n            ++steps;\n        }\n        return -1;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C

Related Tags