문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
풀이
| 3055 | 맞았습니다!! | 2124 | 0 | C++14 / 수정 | 4163 | 1분 전 |
1. 시뮬레이션 비슷한 완전탐색(?)
[비슷한 문제]
2019/10/25 - [BOJ/C++] - [BOJ] 불!
[BOJ] 불!
문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출..
jayrightthere.tistory.com
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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int r, c;
char map[51][51];
typedef pair<int, int> pp;
typedef pair<pp, int> ppp;
queue<ppp> hedgehog;
queue<pp> water;
bool visited[51][51];
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
void print()
{
cout << '\n';
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cout << map[i][j] << ' ';
}
cout << '\n';
}
cout << '\n';
}
void bfs()
{
{
int size = water.size();
while (size--)
{
int wx = water.front().first;
int wy = water.front().second;
water.pop();
for (int i = 0; i < 4; i++)
{
int wnx = wx + dx[i];
int wny = wy + dy[i];
if (wnx < 0 || wnx >= r || wny < 0 || wny >= c || map[wnx][wny] == 'X' || map[wnx][wny] == '*' || map[wnx][wny] == 'D')
continue;
map[wnx][wny] = '*';
}
} //while water
size = hedgehog.size();
while (size--)
{
int cnt = hedgehog.front().second;
hedgehog.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= r || ny < 0 || ny >= c || map[nx][ny] == 'X' || map[nx][ny] == '*' || visited[nx][ny])
continue;
if (map[nx][ny] == 'D'){
cout << cnt + 1 << '\n';
return;
}
if (map[nx][ny] == '.')
{
map[nx][ny] == 'S';
visited[nx][ny] =true;
}
}
}
}
cout << "KAKTUS" << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> r >> c;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> map[i][j];
if (map[i][j] == 'S')
{
visited[i][j] = true;
}
else if (map[i][j] == '*')
{
}
}
}
//input
bfs();
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
[테스트케이스]
5 5
.....
..XXD
...XX
S....
....*
->8
--------------------------------------------------------------------
5 5
*****
XX***
.....
S....
....D
->KAKTUS
--------------------------------------------------------------------
10 15
........X......
..XXXXX.X.*....
X.....X.X..*...
.X.S..X.X......
D.X...X.XXXXXXX
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..
->30
--------------------------------------------------------------------
1 50
S................................................D
->49
--------------------------------------------------------------------
1 50
S..............XD................................*
->KAKTUS
--------------------------------------------------------------------
5 5
*****
XXXXX
*....
S*...
....D
->KAKTUS
--------------------------------------------------------------------
3 4
D...
.*..
S...
->KAKTUS
--------------------------------------------------------------------
3 3
D..
*..
S*.
->KAKTUS
--------------------------------------------------------------------
3 3
DS.
*X.
...
->1
--------------------------------------------------------------------
3 3
DS.
.X.
*..
->1
--------------------------------------------------------------------
2 10
S........D
*.........
->9
--------------------------------------------------------------------
3 5
S....
..D..
....*
->3
--------------------------------------------------------------------
50 50
D.................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.................................................S
'BOJ > C++' 카테고리의 다른 글
| [BOJ] 백조의 호수 (0) | 2019.10.25 |
|---|---|
| [BOJ] 양 (0) | 2019.10.25 |
| [BOJ] 테트리스 (0) | 2019.10.25 |
| [BOJ] 자와 각도기 (0) | 2019.10.24 |
| [BOJ] 안전영역 (0) | 2019.10.24 |
