알고리즘/BOJ

백준 1103번 게임

꾸준함. 2024. 5. 6. 16:23

문제 링크입니다: https://www.acmicpc.net/problem/1103

 

문제 조건대로 풀면 되는 백트래킹 + DP 문제였습니다.

중간에 있는 구멍은 무시한다는 조건이 있기 때문에 동전을 한 칸 한 칸 움직이지 않고 한 번에 이동해도 무방했습니다. 

 

#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;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: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