드롭 존
시간 제한2초메모리 제한128 MB
지도 가장자리에서 낙하 지점으로 통하는 모든 경로를 인접한 열린 칸 사이 방벽으로 가장 적게 차단합니다.
문제
특수팀은 주민 대피 임무와 보급품 확보 임무를 정기적으로 수행한다. 이런 임무에서 가장 먼저 하는 일은 바리케이드로 방어선을 세우는 것이다. 바리케이드는 값이 비싸고 설치하는 데 시간도 걸리므로, 구역을 봉쇄하는 데 드는 바리케이드 개수를 최대한 줄여야 한다.
중요도가 높은 드롭 존의 지도가 여러 장 주어진다. 지도마다 드롭 존을 봉쇄하는 데 필요한 바리케이드의 최소 개수를 구하는 프로그램을 작성하라.
좀비는 지도 바깥에서 접근해 온다. 따라서 지도 경계에 있는 개방 구역에는 모두 좀비가 닿는다. 바리케이드는 인접한 두 개방 구역 사이라면 어디에나 설치할 수 있고, 드롭 존도 개방 구역으로 친다. 지도 바깥의 구역은 전부 개방 구역이다.
지도 경계에 있는 칸은 지도 밖을 향한 변마다 바깥 구역과 맞닿아 있다. 그래서 그 칸을 바깥과 끊으려면 변 하나마다 바리케이드가 하나씩 필요하고, 지도 모서리에 있는 칸이라면 두 개가 필요하다.
입력
첫 줄에 지도의 개수 ()이 주어진다.
지도마다 먼저 한 줄에 행의 개수 과 열의 개수 ()가 주어지고, 이어서 지도가 개의 줄에 걸쳐 주어진다. 각 줄의 길이는 모두 로 같다.
출력
지도마다 드롭 존을 봉쇄하는 데 필요한 바리케이드의 최소 개수를 한 줄에 하나씩 출력한다.