반응형
https://www.acmicpc.net/problem/16509
16509번: 장군
오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해
www.acmicpc.net
[ 문제풀이 ]
1. R1, C1, R2, C2를 입력받고, R1, C1을 queue에 넣고 bfs를 실행합니다.
2. 만약 이동 경로 중간에 말이 있다면 움직이지 않고, 그렇지 않다면 움직입니다.
3. 만약 상이 왕의 위치로 가면 여태 움직인 횟수를 출력하고, 왕을 잡지 못한다면 -1을 출력합니다.
[ 소스코드 ]
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 74 75 76 77 78 79 80 81 | #include<iostream> #include<queue> using namespace std; int R1, C1, R2, C2; int visited[10][9]; int dy[8][3] = { -1,-1,-1, 0,-1,-1, 0,1,1, 1,1,1, 1,1,1, 0,1,1, 0,-1,-1, -1,-1,-1 }; int dx[8][3] = { 0,1,1, 1,1,1, 1,1,1, 0,1,1, 0,-1,-1, -1,-1,-1, -1,-1,-1, 0,-1,-1 }; struct node { int y; int x; int cnt; }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> R1 >> C1 >> R2 >> C2; queue<node> q; q.push({ R1,C1,0 }); visited[R1][C1] = 1; while (!q.empty()) { const int y = q.front().y; const int x = q.front().x; const int cnt = q.front().cnt; q.pop(); if (y == R2 && x == C2) { cout << cnt; return 0; } for (int i = 0; i < 8; i++) { int yy = y; int xx = x; bool flag = true; for (int j = 0; j < 3; j++) { yy += dy[i][j]; xx += dx[i][j]; if (yy == R2 && xx == C2 && j != 2) { flag = false; } } if (yy >= 0 && yy < 10 && xx >= 0 && xx < 9 && flag) { if (visited[yy][xx] != 1) { visited[yy][xx] = 1; q.push({ yy,xx,cnt + 1 }); } } } } cout << -1; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14852번 - 타일 채우기 3 (C++) (0) | 2023.07.30 |
|---|---|
| [ 백준 ] 16954번 - 움직이는 미로 탈출 (C++) (0) | 2023.07.29 |
| [ 백준 ] 15558번 - 점프 게임 (C++) (0) | 2023.07.27 |
| [ 백준 ] 1245번 - 농장 관리 (C++) (0) | 2023.07.26 |
| [ 백준 ] 16934번 - 게임 닉네임 (C++) (0) | 2023.07.25 |