그래프/BFS
나이트의 이동
4gats
2023. 3. 4. 22:09
https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int d[300][300];
int dx[] = {-2,-1,1,2,2,1,-1,-2};
int dy[] = {1,2,2,1,-1,-2,-2,-1};
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int sx,sy;
cin >> sx >> sy;
int ex,ey;
cin >> ex >> ey;
memset(d,-1,sizeof(d));
queue<pair<int,int>> q;
q.push(make_pair(sx,sy));
d[sx][sy] = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<8; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.push(make_pair(nx,ny));
}
}
}
}
cout << d[ex][ey] << '\n';
}
return 0;
}
|
cs |