문제 URL : www.acmicpc.net/problem/17130
17130번: 토끼가 정보섬에 올라온 이유
첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반
www.acmicpc.net
문제접근법 : 토끼는 무조건 앞으로 접근합니다. 그렇지만 →, ↘, ↗ 방향으로만 움직이기때문에 y,x 좌표계를 사용할때 x좌표는 반드시 한칸 증가하는 꼴입니다. 그렇지만 반대로 생각하면
현재 좌표에서 이전에 왼쪽혹은, 왼쪽위, 왼쪽아래 에서 온걸 확인해서 가장 큰것을 dp에 저장해서
O중에서 가장큰것을 리턴하면됩니다.
|
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
|
//By 콩순이냉장고
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
char board[1000][1000];
int dp[1000][1000];
int dy[3] = { -1,0,1 };
int dx[3] = { 1,1,1 };
int sy, sx;
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
if (board[i][j] == 'R')
{
sy = i;
sx = j;
board[i][j] = '.';
}
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
void solve() {
memset(dp, -1, sizeof(dp));
dp[sy][sx] = 0;
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (board[i][j] == '#')//벽이라면 움직이지 못함
continue;
for (int k = 0; k < 3; k++) {
int by = i - dy[k];
int bx = j - dx[k];
if (isrange(by, bx) && dp[by][bx] != -1) { //범위내에 있고 이전좌표들이 시작점을 통과해서 오지 않는 것들이라면 이게 가장중요
if (board[i][j] == 'C') { //이전꺼 당근이면 이전좌표에서 하나더해서 가장큰것을
dp[i][j] = max(dp[i][j], dp[by][bx] + 1);
}
else {
dp[i][j] = max(dp[i][j], dp[by][bx]);//이전꺼 그외 빈공간이나 탈출구나 벽이어도 상관없는게 어차피 -1임
}
}
}
}
}
int Max = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O')
Max = max(dp[i][j], Max);
}
}
cout << Max << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 있다면 언제든 댓글을 이용해주시길 바랍니당
'백준' 카테고리의 다른 글
| 백준 20437 문자열 게임2 (0) | 2021.05.05 |
|---|---|
| 백준 3687 성냥개비 (0) | 2021.04.23 |
| 백준 1600 말이 되고픈 원숭이 (0) | 2021.04.05 |
| 백준 2931 가스관 (0) | 2021.04.05 |
| 백준 14888 연산자 끼워넣기 (0) | 2021.02.17 |
