게시판 구멍 막기
시간 제한2초메모리 제한128 MB
구멍이 있는 격자판에서, 구멍이 아닌 칸은 덮지 않으면서 모든 구멍을 덮는 가로/세로 테이프 조각의 최소 개수를 구하는 문제입니다.
문제
N행 M열 모양의 게시판에 구멍이 뚫려 있다. 폭이 1인 테이프를 사용해 모든 구멍을 막으려 한다.
테이프의 길이는 충분히 길다고 생각해도 되지만, 잘라 내는 테이프 조각의 수를 최소로 해야 한다. 각 테이프 조각은 가로 또는 세로 방향으로만 붙일 수 있다. 구멍이 없는 칸을 덮어서는 안 되며, 이미 테이프가 붙은 구멍 칸 위에 다른 테이프를 다시 붙이는 것은 허용된다.
입력
첫째 줄에 N과 M (1 <= N, M <= 50)이 주어진다.
다음 N개의 줄에는 게시판의 모양을 나타내는 길이 M의 문자열이 주어진다. 구멍이 없는 칸은 ., 구멍이 있는 칸은 *로 표시된다.
출력
잘라 내야 하는 테이프 조각 수의 최솟값을 출력한다.