1103번: 게임

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

DAG로 가정해서 DP로 푸는 동시에 사이클이 존재하는지 확인한다.

시간복잡도는 $O(nm)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, m, dp[50][50], vis[50][50], p[50][50];
char s[50][51];
int f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || s[x][y] == 'H') return 0;
    if (p[x][y]) { puts("-1"); exit(0); }
    int &ret = dp[x][y];
    if (vis[x][y]) return ret;
    p[x][y] = vis[x][y] = 1;
    int t = s[x][y] - '0';
    for (int i = 0; i < 4; i++) ret = max(ret, f(x + t*dx[i], y + t*dy[i]));
    p[x][y] = 0;
    return ++ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    printf("%d", f(0, 0));
    return 0;
}