[백준]게임(미완성)

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

1103번: 게임

 

#include <iostream>
using namespace std;
/*
1.dfs로 탐색하고 사이클이 발견되면 -1이다.
2.사이클은 dfs로 탐색하면서 같은 점을 두번 방문하면 사이클이다.
*/
 
int N, M;
int map[50][50]; //1~9 or 'H=24'
bool isV[50][50];
int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };//상하좌우
int ans = -2;
 
void dfs(int r, int c,int len) {
    if (ans == -1) return; //사이클이 있으면 할 필요가 없음.
    if (r < 0 || c < 0 || r >= N || c >= M || map[r][c] == 24) {
        //len과 ans를 비교해서 최대값 저장    
        if (len >= ans) ans = len;
        return; 
    }
    if (isV[r][c] == true) { ans = -1; return; } //사이클 존재 -1로 끝내야함.
    //printf("%d %d\n", r, c);
 
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i] * map[r][c];
        int nc = c + dc[i] * map[r][c];
        isV[r][c] = true;
        dfs(nr, nc, len + 1);
        isV[r][c] = false;
    }
 
}
 
int main()
{
    cin >> N >> M;
    char a;
    for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> a; map[i][j] = int(a) - 48; } }
    dfs(0, 0, 0);
    printf("%d\n", ans);
    return 0;
}