이번 문제는 DFS와 DP를 이용하여 해결하였다. 처음에는 DFS만으로 탐색하여 시간초과가 발생하였다. 그래서 DP를 통해 해당 좌표에서의 값을 저장하고, 다음 탐색하고자 할 때의 카운팅 변수가 그 좌표의 dp값보다 작을 경우에는 탐색하지 않도록 하는 방식으로 가지치기를 하여 시간을 줄이는 방법을 적용하였다. 무한 이동이 가능한 경우는 방문처리된 좌표에 다시 방문할 수 있을 경우가 해당된다.

Code

n, m=map(int, input().split())
board=[str(input()) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
dp=[[0 for _ in range(m)] for _ in range(n)]
visited=[[False for _ in range(m)] for _ in range(n)]
answer=-1
def get_answer(y, x, cnt):
    global answer
    answer=max(answer, cnt)
    for i in range(4):
        ny, nx=y+int(board[y][x])*dy[i], x+int(board[y][x])*dx[i]
        if 0<=ny<n and 0<=nx<m and board[ny][nx]!='H' and cnt+1>dp[ny][nx]:
            if visited[ny][nx]:
                answer=-1
                print(answer)
                quit()
            else:
                dp[ny][nx]=cnt+1
                visited[ny][nx]=True
                get_answer(ny, nx, cnt+1)
                visited[ny][nx]=False
get_answer(0, 0, 0)
print(answer+1)