[BOJ 1103] 게임

BOJ :: 백준 :: 1103 :: 게임

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

#include <iostream>

#include <algorithm>

using namespace std;

int N, M;

int map[51][51], dp[51][51];

bool visited[51][51];

int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

inline bool check(int i, int j) { return ((i >= 0 && j >= 0 && i < N && j < M) ? true : false); }

int dfs(int i, int j) {

if (!check(i, j) || map[i][j] == 999) return 0;

if (visited[i][j]) {

cout << -1 << endl; exit(0);

}

int &ans = dp[i][j];

if (ans != -1) return ans;

visited[i][j] = true;

for (int d = 0; d < 4; d++) ans = max(ans, dfs(i + dir[d][0] * map[i][j], j + dir[d][1] * map[i][j]) + 1);

visited[i][j] = false;

return ans;

}

int main() {

std::ios::sync_with_stdio(false);

cin >> N >> M; char tmp;

for (int i = 0; i < N; i++) for (int j = 0; j <M; j++) {

scanf(" %c", &tmp); map[i][j] = ((tmp == 'H') ? 999 : tmp - '0'); dp[i][j] = -1;

}

cout << dfs(0, 0) << endl;

return 0;

}