#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N, M, ans=1;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
char board[55][55];
map<pair<pair<int,int>,int>, bool> m;
map<pair<pair<int,int>,int>, int> dp;
void DFS(int y, int x, int cnt)
{
for(int dir=0;dir<4;dir++)
{
int ny = y;
int nx = x;
int len = board[y][x] - '0';
while(len--)
{
ny += dy[dir];
nx += dx[dir];
}
if((nx<0 or ny<0 or ny>=N or nx>=M) or (board[ny][nx] == 'H')){
dp[{{ny,nx},dir}] = max(cnt+1, dp[{{ny,nx},dir}]);
ans = max(ans,cnt+1);
continue;
}
if(m[{{ny,nx},dir}] == true){
cout << -1;
exit(0);
}
if(dp[{{ny,nx},dir}] >= cnt+2){
continue;
}
dp[{{ny,nx},dir}] = cnt+2;
m[{{ny,nx},dir}] = true;
ans = max(ans,cnt+2);
DFS(ny, nx, cnt+1);
m[{{ny,nx},dir}] = false;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
cin >> board[i][j];
for(int dir=0;dir<4;dir++)
{
int ny = 0;
int nx = 0;
int len = board[0][0] - '0';
while(len--)
{
ny += dy[dir];
nx += dx[dir];
}
if((nx<0 or ny<0 or ny>=N or nx>=M) or (board[ny][nx] == 'H')){
dp[{{0,0},dir}] = 1;
ans = max(ans,1);
continue;
}
if(m[{{ny,nx},dir}] == true){
cout << -1;
exit(0);
}
if(dp[{{ny,nx},dir}] >= 2){
continue;
}
ans = max(ans,2);
dp[{{ny,nx},dir}] = 2;
m[{{ny,nx},dir}] = true;
DFS(ny, nx, 1);
m[{{ny,nx},dir}] = false;
}
cout << ans;
return 0;
}
- 필요 기법
백트래킹
+ DP
를 모두 사용
해야 무한 경로 검사
+ 중복 경우 제거(시간 단축)
이 가능
함!
- 핵심
Cycle 검사
: map을 활용
해서 해당 좌표의 해당 방향
으로 이미 온 기록
이 있으면 Cycle로 간주
(백트래킹
이용)
--> 무한대로 도는 경우
를 검사해서 -1 출력
후 exit(0)
메모제이션 기법
으로 중복 제거
: 해당 좌표에 해당 방향
으로 기록된 길이
가 현재 경우보다 크거나 같으면
더이상 할필요가 X
--> 중복을 배제
하여 시간 단축!
- 느낀 점
cycle검사
에 map을 유용
하게 활용
가능
DP의 핵심
인 메모제이션 기법
을 통해서 중복을 배제
할 수 있음 --> 시간 단축