kt_꿀열매

문제

동욱이는 N×M 격자판 미로를 탈출하려고 합니다. 동욱이는 미로를 상하좌우로 한 칸씩 움직입니다. 이때 벽이 없는 칸으로만 이동할 수 있습니다. 미로에는 꿀열매라는 것이 있습니다.
꿀열매를 먹으면 동욱이가 하루 동안 움직일 수 있는 칸의 수가 1 증가합니다. 꿀열매를 먹지 않은 상태의 동욱이는 하루에 한 칸씩 움직일 수 있습니다. 꿀열매는 여러 번 먹어도 효과가 중첩되지 않습니다. 집이 그리운 동욱이는 최적의 방법으로 미로를 탈출합니다. 동욱이가 미로를 탈출하는 데 며칠이 걸리는지 출력하는 프로그램을 작성해 주세요.