문제
문제접근
문제 이해
코드
#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
bool visited[300][300];
int T, I, d[8][2] = {
{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}
};
bool isValid(int y, int x) {
return (0 <= y && y < I && 0 <= x && x < I);
}
int solve(int sy, int sx, int ey, int ex) {
queue<tuple<int, int, int>> q;
q.push({sy, sx, 0});
visited[sy][sx] = true;
while (!q.empty()) {
int cy, cx, cost; tie(cy, cx, cost) = q.front();
if (cy == ey && cx == ex) return cost;
q.pop();
for (int i = 0; i < 8; ++i) {
int ny = cy + d[i][0], nx = cx + d[i][1];
if (isValid(ny, nx) && !visited[ny][nx]) {
visited[ny][nx] = true;
q.push({ny, nx, cost + 1});
}
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
int sy, sx, ey, ex;
cin >> I >> sy >> sx >> ey >> ex;
cout << solve(sy, sx, ey, ex) << '\n';
memset(visited, false, sizeof(visited));
}
}
결과