\(R \times C\) 격자로 이루어진 던전이 있다. 각 칸은 빈 칸(.) 또는 벽(#)이다. 주인공은 왼쪽 위 칸 \((1, 1)\)에서 출발하여 오른쪽 아래 칸 \((R, C)\)의 출구로 가려 한다.

주인공은 상하좌우 인접한 칸으로 이동할 수 있다. 빈 칸으로 이동하는 데에는 비용이 들지 않지만, 벽이 있는 칸으로 이동하려면 그 벽을 부숴야 하며 이때 곡괭이 \(1\)개가 든다(벽을 부수면 그 칸으로 들어갈 수 있다).

출발 칸과 출구 칸도 벽일 수 있는데, 그 칸이 벽이면 그 벽을 부수는 비용도 곡괭이 \(1\)개로 센다. \((1,1)\)에서 \((R,C)\)까지 가는 데 필요한 곡괭이의 최소 개수(부숴야 하는 벽의 최소 개수)를 구하여라.

격자는 사방이 막혀 있지 않으며, 모든 칸은 (벽을 충분히 부수면) 서로 도달 가능하므로 답은 항상 존재한다.

• \(1 \le R, C \le 500\)

첫째 줄에 격자의 크기 \(R\ C\)가 주어진다.

다음 \(R\)개의 줄에 각각 길이 \(C\)의 문자열이 주어지며, .은 빈 칸, #은 벽을 나타낸다.

\((1,1)\)에서 \((R,C)\)까지 가기 위해 부숴야 하는 벽의 최소 개수를 출력한다.

riseoj 작성

출처 Original