문제 링크입니다: https://www.acmicpc.net/problem/1103
문제 조건대로 풀면 되는 백트래킹 + DP 문제였습니다.
중간에 있는 구멍은 무시한다는 조건이 있기 때문에 동전을 한 칸 한 칸 움직이지 않고 한 번에 이동해도 무방했습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <algorithm> | |
#include <cstring> | |
using namespace std; | |
const int MAX = 50; | |
const int INF = 987654321; | |
typedef struct | |
{ | |
int y, x; | |
} Dir; | |
Dir moveDir[4] = { {1,0 }, {-1, 0}, {0, 1}, {0, -1} }; | |
int N, M; | |
string board[MAX]; | |
int cache[MAX][MAX]; | |
bool visited[MAX][MAX]; | |
int func(int y, int x) | |
{ | |
if (y < 0 || y >= N || x < 0 || x >= M) | |
{ | |
return 0; | |
} | |
if (board[y][x] == 'H') | |
{ | |
return 0; | |
} | |
if (visited[y][x]) | |
{ | |
cout << -1 << "\n"; | |
exit(0); | |
} | |
int& result = cache[y][x]; | |
if (result != -1) | |
{ | |
return result; | |
} | |
result = 0; | |
visited[y][x] = true; | |
for (int k = 0; k < 4; k++) | |
{ | |
int nextY = y + moveDir[k].y * int(board[y][x] - '0'); | |
int nextX = x + moveDir[k].x * int(board[y][x] - '0'); | |
result = max(result, 1 + func(nextY, nextX)); | |
} | |
visited[y][x] = false; | |
return result; | |
} | |
int main(void) | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
cin >> N >> M; | |
for (int i = 0; i < N; i++) | |
{ | |
cin >> board[i]; | |
} | |
memset(cache, -1, sizeof(cache)); | |
cout << func(0, 0) << "\n"; | |
return 0; | |
} |

개발환경:Visual Studio 2022
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
백준 12852번 1로 만들기 2 (0) | 2024.05.06 |
---|---|
백준 4811번 알약 (1) | 2024.05.06 |
백준 31796번 한빛미디어 (Easy) (0) | 2024.05.06 |
백준 15989번 1, 2, 3 더하기 4 (0) | 2024.05.05 |
백준 2670번 연속부분최대곱 (0) | 2024.05.05 |