알고리즘 스터디

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

유명한 BFS 문제이다.

평범하게 나이트가 갈 수 있는 좌표를 지정해놓고 범위 안에 있는지, 이미 지나갔었는지 체크하고

답을 구했다

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long int

using namespace std;

vector<int> dx = {-2, -1, 1, 2, 2, 1, -1 ,-2};
vector<int> dy = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m, sx, sy, ex, ey;

bool RouteCheck(int e1, int e2) {
  return e1 >= 0 && e2 >= 0 && e1 < m && e2 < m;
}

void Solve() {
  vector<vector<int>> visit(m, vector<int>(m));
  vector<vector<bool>> ck(m, vector<bool>(m));
  queue<pair<int, int>> q;
  q.push({sx, sy});
  ck[sx][sy] = true;

  while (!q.empty()) {
    auto t = q.front();
    q.pop();

    if (t.first == ex && t.second == ey) {
      cout << visit[ex][ey] << '\n';
      return;
    }

    for (int i = 0; i < 8; ++i) {
      int a = t.first + dx[i];
      int b = t.second + dy[i];

      if (RouteCheck(a, b) && !ck[a][b]) {
        q.push({a, b});
        ck[a][b] = true;
        visit[a][b] = visit[t.first][t.second] + 1;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;

  for (int i = 0; i < n; ++i) {
    cin>>m>>sx>>sy>>ex>>ey;
    Solve();
  }

  return 0;
}