탐험가 아라가 \(R \times C\) 크기의 미로 안에 갇혔다. 미로의 각 칸은 이동 가능한 통로(\(.\))이거나 통과할 수 없는 벽(\(\#\))이다.

아라는 \((1, 1)\)번 칸(왼쪽 위)에서 출발해 \((R, C)\)번 칸(오른쪽 아래)으로 빠져나가야 한다. 한 번에 상하좌우 인접한 칸으로 한 칸씩 이동할 수 있으며, 벽 칸으로는 이동할 수 없다. 시작 칸과 도착 칸은 모두 통로임이 보장된다.

탈출에 필요한 최소 이동 횟수를 구하여라. 탈출이 불가능하면 \(-1\)을 출력한다.

• \(1 \le R, C \le 500\)
• 격자는 \(.\)과 \(\#\)만으로 구성된다.
• \((1, 1)\)과 \((R, C)\)는 항상 통로(\(.\))이다.

첫째 줄에 미로의 행 수 \(R\)과 열 수 \(C\)가 공백으로 구분되어 주어진다.

다음 \(R\)개의 줄에 미로의 각 행이 주어진다. 각 행은 \(C\)개의 문자로 이루어지며 \(.\)또는 \(\#\)이다.

최소 이동 횟수를 출력한다. 탈출이 불가능하면 \(-1\)을 출력한다.

riseoj 작성

출처 Original