문제 URL :https://www.acmicpc.net/problem/1103
1103번: 게임
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는
www.acmicpc.net
문제 접근법 : dfs + 메모이제이션 + 사이클 확인문제이다
사이클은 간단하게 왔던곳 또왔는지체크해주면 됩니다.
그리고 문제요구대로 좌우상하 나가지 않고 최대 오랫동안 버틸수있는지 돌려봅니다.
그것들중에 max값 확인해서 메모이제이션 으로 처리해주면 됩니다.
소스코드 :
|
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
|
#include<bits/stdc++.h>
using namespace std;
char board[50][50];
int dp[50][50];
int check[50][50];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m;
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
int dfs(int y, int x) {
if (!isrange(y, x)) return 0;
if (board[y][x] == 'H')return 0;
int& res = dp[y][x];
if (check[y][x])return 1e8;
if (res != -1)return res;
check[y][x] = 1;
for (int i = 0; i < 4; i++) {
int jump = board[y][x] - '0';
int ny = y + dy[i] * jump;
int nx = x + dx[i] * jump;
res = max(res, dfs(ny, nx) + 1);
}
check[y][x] = 0;
return res;
}
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> board[i][j];
}
void solve(){
memset(dp, -1, sizeof(dp));
int res = dfs(0, 0);
cout << (res>=1e8?-1:res) << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나
환여입니다.
'백준' 카테고리의 다른 글
| 백준 16437 양 구출 작전 (0) | 2022.05.17 |
|---|---|
| 백준 2688 줄어들지 않아 (0) | 2022.04.07 |
| 백준 20005 보스몬스터 전리품 (0) | 2022.03.30 |
| 백준 9328 열쇠 (0) | 2022.03.29 |
| 백준 17140 이차원 배열과 연산 (0) | 2022.03.29 |
