문제
R 행 C 열 직사각형 크기를 갖는 농부 재우(FJ-Farmer Jaewoo)의 목장에 비가 내려 내렸다. (1 <= R <= 50, 1 <= C <= 50)
비는 자라는 풀들에는 좋았지만 목초지의 일부를 진창(땅이 질어서 질퍽하게 된 곳)으로 만들었다.
깔끔하고 세심한 FJ의 소들은 발굽이 더러워지는 것을 매우 싫어한다.
그 진흙 발굽을 방지하기 위해 농장주 FJ는 목장의 진창들 위에 여러 개의 나무 판을 놓을 생각이다.
각 나무판은 너비가 1 단위이며 다양한 길이를 갖는다.
각 나무판은 수직 또는 수평으로 놓여져야 한다.
농장주 FJ는 진창들을 덮는 데 필요한 나무판 수를 최소화하기를 원하며,
일부 진창들을 덮는데 두 개 이상의 나무판이 사용될 수도 있다.
한 곳의 진창에 두 개 이상의 나무판을 포개놓을 수 있지만 나무판이 풀을 덮을 수는 없다.
FJ가 목장의 모든 진흙을 덮는 데 필요한 최소 보드 수를 계산하십시오.
입력
첫째 줄에 R, C(1≤R, C≤50)이 주어진다.
다음 R개의 각 줄에는 C개의 문자(들)로 목장의 정보가 주어진다.
풀은 '.'으로, 진창은 '*'로 주어진다.
출력
FJ(농부 재우)가 사용하는 판자 수의 최소값을 출력한다.
예제1
입력
44
*.*.
.***
***.
..*.
출력
4
힌트
출처
USACO January 2005 Contest Gold 1번 Muddy Fields