드롭 존 | cho.sh

특수팀은 주민 대피 임무와 보급품 확보 임무를 정기적으로 수행한다. 이런 임무에서 가장 먼저 하는 일은 바리케이드로 방어선을 세우는 것이다. 바리케이드는 값이 비싸고 설치하는 데 시간도 걸리므로, 구역을 봉쇄하는 데 드는 바리케이드 개수를 최대한 줄여야 한다.

중요도가 높은 드롭 존의 지도가 여러 장 주어진다. 지도마다 드롭 존을 봉쇄하는 데 필요한 바리케이드의 최소 개수를 구하는 프로그램을 작성하라.

좀비는 지도 바깥에서 접근해 온다. 따라서 지도 경계에 있는 개방 구역에는 모두 좀비가 닿는다. 바리케이드는 인접한 두 개방 구역 사이라면 어디에나 설치할 수 있고, 드롭 존도 개방 구역으로 친다. 지도 바깥의 구역은 전부 개방 구역이다.

지도 경계에 있는 칸은 지도 밖을 향한 변마다 바깥 구역과 맞닿아 있다. 그래서 그 칸을 바깥과 끊으려면 변 하나마다 바리케이드가 하나씩 필요하고, 지도 모서리에 있는 칸이라면 두 개가 필요하다.

기호	설명
`X`	통과할 수 없는 구역. 좀비가 지나가지 못한다.
`.`	개방 구역. 좀비는 상하좌우로만 움직이고 대각선으로는 움직이지 못한다. 개방 구역 사이에는 바리케이드를 설치할 수 있다.
`D`	드롭 존. 무슨 수를 써서라도 지켜야 하는 구역이다. 지도 가장자리에서 이 구역으로 들어오는 좀비의 경로를 바리케이드로 빠짐없이 막아야 한다. 좀비의 이동과 바리케이드 설치에서는 개방 구역과 똑같이 취급한다. 모든 지도에는 서로 이어진 드롭 존이 정확히 하나 있다. 드롭 존이 지도 가장자리에 걸쳐 있을 수도 있다.

첫 줄에 지도의 개수 $N$ ( $1 \le N \le 20$ )이 주어진다.

지도마다 먼저 한 줄에 행의 개수 $R$ 과 열의 개수 $C$ ( $1 \le R, C \le 150$ )가 주어지고, 이어서 지도가 $R$ 개의 줄에 걸쳐 주어진다. 각 줄의 길이는 모두 $C$ 로 같다.

지도마다 드롭 존을 봉쇄하는 데 필요한 바리케이드의 최소 개수를 한 줄에 하나씩 출력한다.