벽을 부수는 미로
면접 대비시간 제한1초메모리 제한128 MB
격자 미로에서 상하좌우로 이동하여 왼쪽 위 방에서 오른쪽 아래 방까지 가는 데 부숴야 하는 벽의 최소 개수를 구하는 문제입니다.
문제
세로 N, 가로 M 크기의 미로가 있다. 미로는 1 * 1 크기의 방으로 이루어져 있으며, 각 방은 빈 방이거나 벽이다. 빈 방으로는 자유롭게 이동할 수 있지만, 벽은 부수어야만 지나갈 수 있다.
여러 사람이 함께 이동하지만, 항상 모두 같은 방에 있어야 한다. 현재 위치가 (x, y)일 때 상하좌우로 인접한 방인 (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)로 이동할 수 있다. 단, 미로 밖으로는 이동할 수 없다.
벽을 부수면 그 방은 빈 방처럼 이동할 수 있는 방이 된다.
처음에 (1, 1)에 있을 때 (N, M)까지 이동하기 위해 부수어야 하는 벽의 최소 개수를 구하라.
입력
첫째 줄에 미로의 가로 크기 M과 세로 크기 N이 주어진다. (1 <= N, M <= 100)
다음 N개의 줄에는 미로의 상태가 길이 M인 문자열로 주어진다. 각 문자는 0 또는 1이다. 0은 빈 방, 1은 벽을 의미한다.
(1, 1)과 (N, M)은 항상 빈 방이다.
출력
첫째 줄에 (1, 1)에서 (N, M)으로 이동하기 위해 부수어야 하는 벽의 최소 개수를 출력한다.