바리스타의 힘

토끼 마을을 모험하던 중학생 토끼 삼총사는 미로를 마주하게 되었습니다. 미로는 세로 길이 N, 가로 길이 M인 N × M 격자 모양입니다. 격자의 각 칸은 위에서부터 i 번째, 왼쪽에서부터 j 번째 칸을 (i, j)로 표기합니다. 따라서 맨 왼쪽 위 칸은 (1, 1)이고, 맨 오른쪽 아래 칸은 (N, M)입니다. 미로의 일부 칸에는 벽이 있을 수도 있습니다. 단, (1, 1)과 (N, M)에는 언제나 벽이 없습니다.

삼총사는 미로를 통과하기 위해 (1, 1)에서 (N, M)까지 가장 적은 이동 횟수로 이동하려고 합니다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입니다. 단, 벽이 있는 칸으로는 이동할 수 없습니다.

삼총사 중 장래희망이 바리스타인 파랑 토끼는 특별한 기술 “바리스타의 힘”을 사용할 수 있습니다. 어떤 칸에서 상하좌우 중 한 방향을 정해 기술을 사용하면 그 방향에 있는 모든 칸의 벽이 사라집니다. 원래 벽이 없는 칸에는 아무 일도 일어나지 않습니다. 다만, 기술을 너무 남용하면 모험이 시시해지므로 “바리스타의 힘”은 최대 한 번까지만 사용하기로 했습니다.

미로의 지도가 주어지면, (1, 1)에서 (N, M)까지 이동할 때 이동 횟수의 최솟값을 구해봅시다.

첫 번째 줄에 두 개의 자연수 N과 M이 주어집니다. (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000)

두 번째 줄부터 N개의 줄에 각 줄마다 0과 1로만 이루어진 길이 M의 문자열이 한 개씩 주어집니다.

i + 1번째 줄 j번째 문자가 0이면 (i, j)에 벽이 없다는 뜻이고, 1이면 벽이 있다는 뜻입니다. (1, 1)과 (N, M)에 벽이 없는 입력만 주어집니다.

첫 번째 줄에 이동 횟수의 최솟값을 출력합니다. 미로를 통과할 수 없다면 -1을 출력합니다.