문제

• 나이트가 한번에 이동할 수 있는 칸
  dx={-2,-1,1,2,2,1,-1,-2}
  dy={1,2,2,1,-1,-2,-2,-1}
• 나이트가 최소 몇번만에 이동하려는 칸에 도착하는지 출력

풀이

풀이 1

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
int dist[305][305];
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int T, n, x, y, tx, ty;
queue <pair<int, int >> Q;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> T;
  while (T--) {
    cin >> n;
    
    for (int i = 0; i < n; i++) 
        fill(dist[i], dist[i] + n, -1);
    
    //현재 위치   
    cin >> x >> y;
    dist[x][y] = 0;
    Q.push({x, y});
    
    //이동하려고 하는 칸
    cin >> tx>>ty;
    
    while (!Q.empty()) {
      auto cur = Q.front(); Q.pop();
      for (int dir = 0; dir < 8; dir++) {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (dist[nx][ny] >= 0) continue;
        dist[nx][ny] = dist[cur.X][cur.Y] + 1;        
        Q.push({nx, ny});
      }
    }
    cout << dist[tx][ty] << "\n";
  }
}