게임

도움이 된 TC

5 7
3994995
9999999
4H99399
9999999
2993994

ans = 6

3 4
3552
5555
2553

ans = -1

4 3
133
5HH
HHH
21H

ans = 5

4 4
12H3
2H3H
HHHH
41H2

5 5
13HH2
2HHHH
HHHH2
HHHHH
3HHH4

5 5
13HH1
HHHH3
3HH2H
HHHHH
2HH31

5 5
4H3H2
HHHHH
HHHHH
HH2HH
1HHH4

5 5
4H3H2
HHHHH
HHHHH
HH2HH
1HHH4

3 3
2H1
3H2
HHH

3 3
2H1
HH2
HHH


3 3
2H1
HH1
HHH

5 5
4HHH9
HHHHH
HHH12
HHHHH
3HH2H

ans = 6

6 7
12HHHHH
2214HHH
H1HHHHH
H4H9H2H
HHHHHHH
HHH2HHH

ans = 7

 

*방문 했던 좌표를 또 가게 된다면 무한 루프가 될 가능성이 있음 -> 바로 -1을 출력하고 종료한다.

*마지막에 +1을 더해주는 이유는 맨 처음 (0,0)에서 굴리는 횟수를 더해주기 위해서이다. 

#include <iostream>
#include <vector>
 
using namespace std;
int n, m;
int map[51][51];
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
bool visited[51][51];
int dp[51][51];
 
bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == -1) return false;
    return true;
}
int dfs(int x, int y) {
    
    if (dp[x][y]) return dp[x][y];
 
    int &ret = dp[x][y];
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i] * map[x][y];
        int ny = y + dy[i] * map[x][y];
 
        if (check(nx, ny)) {
            if (visited[nx][ny]) {
                cout << -1 << '\n';
                exit(0);
            }
            
            visited[nx][ny] = true;
            ret = max(ret,dfs(nx, ny)+1);
            visited[nx][ny] = false;
 
        }
    }
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
 
        for (int j = 0; j < m; j++) {
            if (s[j] == 'H') map[i][j] = -1;
            else {
                map[i][j] = s[j] - '0';
            }
        }
    }
 
    
    visited[0][0] = true;
 
    cout << dfs(0,0)+1 << '\n';
 
   
    return 0;
}