시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1935 | 681 | 543 | 34.432% |
N×M 모양의 게시판에 구멍이 뚫려 있다. 이를 폭이 1인 테이프를 이용하여 막으려 한다. 테이프의 길이는 무한하다고 생각해도 좋지만, 테이프를 끊어내는 횟수를 최소로 하려 한다. 테이프를 붙일 때에는 구멍이 뚫려 있지 않은 부분을 막아서는 안 된다. 하지만 테이프가 한 번 붙은 곳에 테이프를 또 붙여도 된다. 또한, 테이프를 붙일 때에는 가로나 세로로 붙이는 경우만 허용한다.
첫째 줄에 N, M(1 ≤ N, M ≤ 50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.
', 구멍이 있는 부분은 '*
'으로 주어진다.
첫째 줄에 테이프를 끊어 내는 횟수의 최솟값을 출력한다.
4 4 *.*. .*** ***. ..*.
4