문제
풀이
BFS를 이용한 문제이다. 기본 코드에서 크게 다르지 않으며, 다만 이동 경로만 조건에 맞게 수정하면 된다. main의 For 문안에서 vector, queue 들이 선언이 계속 되기 때문에, 초기화 해주는 코드를 넣어주었다.
소스 코드
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int main(){
int testcase;
scanf("%d", &testcase);
for(int i = 0; i<testcase; i++){
int leng;
scanf("%d", &leng);
int start_y, start_x, dest_y, dest_x;
scanf("%d %d", &start_y, &start_x);
scanf("%d %d", &dest_y, &dest_x);
int check[300][300];
for(int i = 0; i<300; i++){
for(int j = 0; j<300; j++){
check[i][j] = 0;
}
}
queue<pair<int, int>> q;
while(!q.empty()){
q.pop();
}
q.push(make_pair(start_y, start_x));
bool visit[300][300];
for(int i = 0; i<300; i++){
for(int j = 0; j<300; j++){
visit[i][j] = false;
}
}
while(!q.empty()){
int x = q.front().second;
int y = q.front().first;
q.pop();
if(x == dest_x && y == dest_y){
printf("%d\n", check[y][x]);
break;
}
for(int i = 0; i<8; i++){
int next_x = x + dx[i];
int next_y = y + dy[i];
if(next_y >= 0 && next_y < leng && next_x >= 0 && next_x < leng){
if(visit[next_y][next_x] == false){
visit[next_y][next_x] = true;
q.push(make_pair(next_y, next_x));
check[next_y][next_x] = check[y][x] + 1;
}
}
}
}
}
}
