코딩공작소
[백준]말이 되고픈 원숭이 본문
https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.
www.acmicpc.net
벽 부수고 이동하기2 와 비슷한 문제였던거 같다.
|
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
|
#include <iostream>
#include <queue>
using namespace std;
struct INFO {
int r, c, k;
};
int K, N, M;
int map[200][200], isV[200][200][31];
int jr[] = { -1,-2,-2,-1,1,2,2,1 }, jc[] = { -2,-1,1,2,-2,-1,1,2 }, dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
queue<INFO> q;
void solve() {
while (!q.empty()) {
int r = q.front().r, c = q.front().c, k = q.front().k; q.pop();
if (r == N - 1 && c == M - 1) { printf("%d\n", isV[r][c][k]); return; }
if (k > 0) {
for (int i = 0; i < 8; i++) {
int nr = r + jr[i], nc = c + jc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M || isV[nr][nc][k - 1] || map[nr][nc] == 1)continue;
q.push({ nr,nc,k - 1 });
isV[nr][nc][k - 1] = isV[r][c][k] + 1;
}
}
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M || isV[nr][nc][k] || map[nr][nc] == 1) continue;
q.push({nr, nc, k});
isV[nr][nc][k] = isV[r][c][k] + 1;
}
}
printf("-1\n");
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> K >> M >> N;
for (int i = 0; i < N; i++)for (int j = 0; j < M; j++) { cin >> map[i][j]; }
q.push({ 0,0,K });
solve();
return 0;
}
|
cs |
'알고리즘 > 그래프' 카테고리의 다른 글
| [프로그래머스]단어변환 (0) | 2019.10.26 |
|---|---|
| [프로그래머스]네크워크 (0) | 2019.10.26 |
| [백준]달이차오른다,가자 (0) | 2019.10.08 |
| [백준]영역구하기 (0) | 2019.10.08 |
| [백준]낚시왕(2) (0) | 2019.09.28 |