N×M 미로에서 0은 길, 1은 벽이에요. 왼쪽 위에서 오른쪽 아래로 가는데, 벽은 몇 개든 부술 수 있지만 최대한 적게 부수고 싶어요. 부숴야 하는 벽의 최소 개수를 구하세요.
힌트: 벽을 부수는 이동은 비용 1, 그냥 이동은 비용 0인 최단 경로예요.
입력
첫째 줄에 N과 M이 주어져요. (1 ≤ N, M ≤ 50) 다음 N줄에 0과 1로 된 길이 M의 문자열이 주어져요. 시작 칸과 도착 칸은 0이에요.
출력
부숴야 하는 벽의 최소 개수를 출력해요.