BOJ - 7562 ) 나이트의 이동

개발자가될수있을까? 2020. 1. 17. 15:06

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

7562번: 나이트의 이동

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...

www.acmicpc.net

나이트가 이동할수 있는 경로를 FOR문으로 설정하여서 돌려준다.

VISIT 배열로 갔던곳을 다시 가지않게 설정해준다.

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

#include <iostream>
#include <queue>
 
using namespace std;
int L , TC;
int start_x, start_y, end_x, end_y;
int map[301][301];
int ans[301];
bool visit[301][301];
void input() {
    cin >> TC;
}
 
 
 
 
typedef struct {
    int x, y, step;
}coordi;
 
int dx[] = {2,1,-1,-2,-2,-1,1,2};
int dy[] = {1,2,2,1,-1,-2,-2,-1};
 
int main(void){
    input();
    for (int i = 0 ; i < TC; i ++) {
        cin >> L;
        for (int y = 0; y < L; y++) {
            for (int x = 0; x < L; x++) {
                map[y][x] = 0;
                visit[y][x] = false;
            }
        }
        int res = 0;
        cin >> start_x >> start_y;
        cin >> end_x >> end_y;
        coordi start = { start_x, start_y, 0 };
 
        queue <coordi> Q;
        Q.push(start);
        while (!Q.empty()){
 
            int x = Q.front().x;
            int y = Q.front().y;
            int step = Q.front().step;
            if (x == end_x && y == end_y) {
                res = step;
                break;
            }
            Q.pop();
 
            for (int index = 0; index < 8; index++) {
                int nx = x + dx[index];
                int ny = y + dy[index];
 
                if (nx >= 0 && ny >= 0 && nx < L && ny < L) {
                    if (!visit[ny][nx]) {
                        visit[ny][nx] = true;
                        Q.push({ nx,ny,step + 1 });
                    }
                }
            }
        }
        
        ans[i] = res;
    }
    for (int index = 0; index < TC; index++) {
        cout << ans[index] << "\n";
    }
 
    return 0;
}

 