BOJ 7562, 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1

예제 출력 1

5
28
0

내 구현

#include <cstring>
#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#include <queue>

#define MAX 301

int dist[MAX][MAX];
int T, L, SC, SR, DC, DR;

int dc[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dr[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

void bfs(int c, int r) {
  std::queue<std::pair<int, int>> Q;
  Q.push({c, r});
  dist[r][c] = 1;

  while (!Q.empty()) {
    auto [qc, qr] = Q.front();
    Q.pop();

    if (qc == DC && qr == DR) {
      std::cout << dist[qr][qc] - 1 << '\n';
      break;
    }

    for (int i = 0; i < 8; i++) {
      int nc = qc + dc[i];
      int nr = qr + dr[i];

      if (0 <= nc && 0 <= nr && nc < L && nr < L && dist[nr][nc] == 0) {
        Q.push({nc, nr});
        dist[nr][nc] = dist[qr][qc] + 1;
      }
    }
  }
}

void solve() {
  std::cin >> T;

  while (T--) {
    std::cin >> L >> SC >> SR >> DC >> DR;
    memset(dist, 0, sizeof(dist));

    bfs(SC, SR);
  }
}

int main() {
  IO;
  solve();
  return 0;
}