1103번 게임

https://www.acmicpc.net/problem/1103

dp cycle 사이클 동적 계획 dfs 복습 필수 코테 boj 백준 싸이클

사이클 여부 및 그냥 구현 문제이다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 52
 
int R, C, cache[5][Max][Max];
bool visit[Max][Max];
vector<pair<int, int> > v;
char m[Max][Max];
 
int dfs(int dir, int r, int c)
{
    if (r < 0 || r >= R || c < 0 || c >= C) {
        return 0;
    }
 
    if (m[r][c] == 'H') {
        return 0;
    }
 
    int &ret = cache[dir][r][c];
    if (ret != -1) {
        return ret;
    }
 
    if (visit[r][c]) {
        printf("-1\n");
        exit(0);
    }
 
    ret = 0;
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++) {
        int moving = m[r][c] - '0';
 
        // 우
        if (i == 0) {
            ret = max(ret, dfs(i, r, c + moving) + 1);
        }
        // 하
        else if (i == 1) {
            ret = max(ret, dfs(i, r + moving, c) + 1);
        }
        // 좌
        else if (i == 2) {
            ret = max(ret, dfs(i, r, c - moving) + 1);
        }
        // 상
        else {
            ret = max(ret, dfs(i, r - moving, c) + 1);
        }
    }
 
    visit[r][c] = false;
 
    return ret;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    memset(cache, -1, sizeof(cache));
 
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
        }
    }
 
    printf("%d\n", dfs(0, 0, 0));
 
    return 0;
}