https://www.acmicpc.net/problem/7562
나이트는 가로로 2칸 세로로 1칸 혹은 가로로 1칸 세로로 2칸씩 이동합니다
그에 따라 dx[], dy[]를 설정할 때 실수가 없으면 간단하게 풀 수 있는 BFS문제입니다
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 | #include <iostream> #include <queue> using namespace std; int dx[] = { 1,1,-1,-1,2,2,-2,-2 }; int dy[] = { 2,-2,2,-2,1,-1,1,-1 }; struct pos { int x; int y; }; int main() { int t; cin >> t; for (int zs = 1; zs <= t; zs++) { int n; cin >> n; int map[301][301] = { 0, }; pos a[2]; queue<pos>q; for (int i = 0; i < 2; i++) { cin >> a[i].x >> a[i].y; } q.push({ a[0].x,a[0].y }); map[a[0].x][a[0].y] = 1; while (!q.empty()) { int kx = q.front().x; int ky = q.front().y; q.pop(); for (int z = 0; z < 8; z++) { int nx = kx + dx[z]; int ny = ky + dy[z]; if (nx >= 0 && nx < n&&ny >= 0 && ny < n&&map[nx][ny] == 0) { map[nx][ny] = map[kx][ky] + 1; q.push({ nx,ny }); } } if (map[a[1].x][a[1].y] != 0) break; } cout << map[a[1].x][a[1].y]-1 << '\n'; } } | cs |
'알고리즘 > BFS 문제풀이' 카테고리의 다른 글
[B3055] - 탈출 (0) | 2018.11.30 |
---|---|
[B5014] - 스타트링크 (0) | 2018.08.26 |
[S1953] - [모의 SW 역량테스트] 탈주범검거 (0) | 2018.08.25 |
[S1249] - 보급로 (0) | 2018.08.25 |
[B14442]-벽 부수고 이동하기2 (0) | 2018.08.24 |