시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 160 MB 780 190 129 21.791%

문제

도현이가 사는 도시는 N*M 크기의 모양이며, 1*1칸으로 나누어져 있다. 각 칸은 빈 칸 또는 벽이다.

도현이는 학교에 가려고 한다. 도현이가 있는 곳은 항상 빈 칸이고, 학교도 빈 칸에 있다. 도현이는 현재 있는 칸과 상하좌우로 인접한 칸으로 이동할 수 있다. 이 때, 벽이 있는 칸으로는 이동할 수 없다. 또, 도시를 벗어날 수는 없다.

준규는 도현이가 학교에 가지 못하게 빈 칸을 적절히 벽으로 바꾸려고 한다. 이미 벽인 곳은 벽으로 바꿀 수 없고, 빈 칸만 벽으로 바꿀 수 있다. 도현이와 학교가 있는 곳은 벽으로 바꿀 수 없다.

도현이가 학교에 가지 못하게 하기 위해서 빈 칸을 벽으로 바꿔야하는 횟수의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. K와 H는 하나만 주어진다.

출력

첫째 줄에 도현이가 학교를 가지 못하게 하기 위해서 바꿔야 하는 벽의 최소 개수를 출력한다. 만약, 벽을 아무리 세워도 학교에 가는 것을 막을 수 없다면 -1을 출력한다.

예제 입력

4 5
K....
...##
##...
....H

예제 출력

1

힌트

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: kkw564