미로에서 1은 길, 0은 벽이에요. 왼쪽 위에서 오른쪽 아래까지 가는데, 특별한 망치로 벽을 딱 한 개까지 부술 수 있어요. 출발 칸과 도착 칸을 포함해 지나는 최소 칸 수를 구하세요.
힌트: 벽을 이미 부쉈는지 여부까지 상태에 넣어서 탐색해야 해요.
입력
첫째 줄에 세로 N과 가로 M이 주어져요. (2 ≤ N, M ≤ 50) 다음 N개의 줄에 0과 1로 이루어진 길이 M의 문자열이 주어져요. 출발 칸과 도착 칸은 항상 1이에요.
출력
최소 칸 수를 출력해요. 벽을 하나 부숴도 도착할 수 없으면 -1을 출력해요.