벽 부수고 이동하기

N×M 미로에서 (1,1)부터 (N,M)까지의 최단 거리를 구한다. 1은 벽, 0은 빈 칸이다. 벽을 최대 1개 부수고 이동할 수 있다. 도달할 수 없으면 -1을 출력한다. 이동은 상하좌우 4방향이며, 한 번 이동할 때마다 거리가 1 증가한다. 시작 칸과 끝 칸도 거리에 포함한다. 벽을 부수지 않아도 된다. BFS 상태에 "벽을 부쉈는지 여부"를 함께 관리한다. ## 입력 첫째 줄에 N과 M이 주어진다. 다음 N개 줄에 M개의 0 또는 1이 공백 없이 주어진다. - 1 ≤ N, M ≤ 1,000 ## 출력 최단 거리를 출력한다. 도달할 수 없으면 -1을 출력한다. ## 예제 입력 1 ``` 6 4 0100 1110 1000 0000 0111 0000 ``` ## 예제 출력 1 ``` 15 ```