---
tags: leetcode
---

# [1197. Minimum Knight Moves](https://leetcode.com/problems/minimum-knight-moves/)
---
# My Solution
## The Key Idea for Solving This Coding Question
BFS
## C++ Code

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

#define ROWS (601)
#define COLS (601)
#define MAX_R (300)
#define MIN_R (-300)
#define MAX_C (300)
#define MIN_C (-300)
#define SHIFT (300)

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

class Solution {
public:
    int minKnightMoves(int x, int y) {
        queue<cell> q;
        vector<vector<int>> dirs = {{-2, 1}, {-2, -1}, {2, 1}, {2, -1}, {1, 2}, {-1, 2}, {1, -2}, {-1, -2}};
        vector<vector<int>> state(ROWS, vector<int>(COLS, WHITE));
        int minLen = 0;

        q.push(cell(0, 0));
        state[getRow(0)][getCol(0)] = GRAY;
        while (!q.empty()) {
            int qLen = q.size();

            for (int i = 0; i < qLen; ++i) {
                cell curr = q.front();
                q.pop();

                if (curr.r == x && curr.c == y) {
                    return minLen;
                }

                for (auto &dir : dirs) {
                    int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                    if (nextR < MIN_R || MAX_R < nextR || nextC < MIN_C || MAX_C < nextC ||
                        state[getRow(nextR)][getCol(nextC)] != WHITE) {
                        continue;
                    }
                    q.push(cell(nextR, nextC));
                    state[getRow(nextR)][getCol(nextC)] = GRAY;
                }
                state[getRow(curr.r)][getCol(curr.c)] = BLACK;
            }
            ++minLen;
        }

        return minLen;
    }

private:
    int getRow(int r) {
        return r + SHIFT;
    }
    int getCol(int c) {
        return c + SHIFT;
    }
};

## Time Complexity
$O(x \cdot y)$
$x$ is the value of parameter `x`.
$y$ is the value of parameter `y`.
## Space Complexity
$O(x \cdot y)$
$x$ is the value of parameter `x`.
$y$ is the value of parameter `y`.
# Miscellaneous
<!--
# Test Cases

2
1

5
5

-->