https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.
www.acmicpc.net
|
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
|
#include<stdio.h>
#include<queue>
#define MSIZE 201
#define NSIZE 201
#define HORSESIZE 31
using namespace std;
int N, M, K;
int input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE][HORSESIZE];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
int ddy[] = { -2,-2,-1,1,2,2,1,-1 };
int ddx[] = { -1,1,2,2,1,-1,-2,-2 };
struct Data {
int y, x, cnt, Horse_mode;
};
void init() {
scanf("%d", &K);
scanf("%d %d", &M, &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &input[i][j]);
}
}
}
void bfs() {
queue<Data>q;
q.push({ 0,0,0,0 });
chk[0][0][0] = 1;
while (!q.empty()) {
Data c = q.front(); q.pop();
if (c.y == N - 1 && c.x == M - 1) {
printf("%d\n", c.cnt);
return;
}
for (int dir = 0; dir < 4; dir++) {
Data n;
n.y = c.y + dy[dir];
n.x = c.x + dx[dir];
n.cnt = c.cnt + 1;
n.Horse_mode = c.Horse_mode;
if (0 <= n.y && n.y < N && 0 <= n.x && n.x < M) {
if (chk[n.y][n.x][n.Horse_mode] == 0 && input[n.y][n.x] == 0) {
chk[n.y][n.x][n.Horse_mode] = 1;
q.push(n);
}
}
}
for (int dir = 0; dir < 8; dir++) {
Data n;
n.y = c.y + ddy[dir];
n.x = c.x + ddx[dir];
n.cnt = c.cnt + 1;
n.Horse_mode = c.Horse_mode + 1;
if (0 <= n.y && n.y < N && 0 <= n.x && n.x < M) {
if (n.Horse_mode <= K && chk[n.y][n.x][n.Horse_mode] == 0 && input[n.y][n.x] == 0) {
chk[n.y][n.x][n.Horse_mode] = 1;
q.push(n);
}
}
}
}
printf("-1\n");
}
int main(void) {
init();
bfs();
}
|
이런문제에서 절대 두려워 하지 않아도 됩니다. 저도 푸는 문제니까요.
이문제는 기존의 bfs에 그냥 말이 이동할 수 있는 것도 갈 수있게 하면됩니다.
기존은 이동을 얼마나 했는지 넣으면서 돌렸다면 이것은 말모드를 몇번 사용했는지를 가지고 돌면되는것이죠
여기 부분을 보시면 한개 더 있죠?
그것을 그냥 말모드로 이동시 +1 씩 증가시키고 입력으로 주어진 K가 되면 더이상 말모드는 사용을 못하게 하면됩니다.
여기서 제가 쓰는 dy, dx 선정은
이렇게 경로를 주고
위아래옆은
말의 이동방향 ( 장기에서 상이 이렇게 움직였죠?, 체스에서는 나이트였나?) 대신
가는길에 장애물이 있어도 넘어갈 수 있다는점
혹시 이문제 풀고 좀더 잘하고 싶다하면 장군 문제 푸시는것 추천드려요
2019/09/21 - [분류 전체보기] - 백준 16509 장군
백준 16509 장군
https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는..
3dpit.tistory.com
오늘은 여기까지이고 파이팅하세요!!!! 정말 잘할수 있습니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 15662 톱니바퀴(2) (0) | 2019.09.29 |
|---|---|
| 백준 1194 달이 차오른다, 가자. (0) | 2019.09.25 |
| 백준 16637 괄호 추가하기 (0) | 2019.09.22 |
| 백준 16509 장군 (0) | 2019.09.21 |
| 백준 9328 열쇠 (0) | 2019.09.19 |
댓글