[7562] 나이트의 이동

내 코드

#include <iostream>
#include <queue>
#include <utility>
int dist[300][300];
int xdis[8] = {2,1,-2,-1,2,1,-1,-2};
int ydis[8] = {-1,-2,1,2,1,2,-2,-1};
using namespace std;

int main(void)
{
    int t; cin >> t;
    while(t--)
    {
        int n; cin >> n;
        for(int i =0;i<n;i++)
        {
            for(int j = 0;j<n;j++)
            {
                dist[i][j] = -1;
            }
        }
        int v,w; cin >> v >> w;
        dist[v][w] = 0;
        queue<pair<int,int>> q;
        q.push({v,w});
        int k,l;
        cin >> k >> l;
        while(!q.empty())
        {
            pair<int,int> cur = q.front(); q.pop();
            for(int i = 0;i<8;i++)
            {
                int curx = cur.first + xdis[i];
                int cury = cur.second + ydis[i];
                if(curx<0||curx>=n||cury<0||cury>=n) continue;
                if(dist[curx][cury] >=0 ) continue;
                q.push({curx,cury});
                dist[curx][cury] = dist[cur.first][cur.second] + 1;
            }
        }
        cout << dist[k][l] << '\n';
        
    }
    return 0;
    
}

• 다른 bfs 문제들과 다르게 8방면 으로 이동가능한 점이 특징이다.
• 불!(https://www.acmicpc.net/problem/4179) 문제와 다르게 최단거리를 바로 출력할 필요 없이, dist 배열을 모두 채우고 목표지점의 dist값 만 출력하면 된다!

정답

#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, xx, yy;
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 >> xx >> yy;
    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[xx][yy] << "\n";
  }
}