USACO January 2005 Contest Gold 1번 Muddy Fields- 진흙 밭(잡초덮기) > 문제은행 : 정보올림피아드&알고리즘




3639 : 진흙 밭(잡초덮기)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
7 회   
시도횟수
14 회   

문제

R 행 C 열 직사각형 크기를 갖는 농부 재우(FJ-Farmer Jaewoo)의 목장에 비가 내려 내렸다.
(1 <= R <= 50, 1 <= C <= 50)

비는 자라는 풀들에는 좋았지만 목초지의 일부를 진창(땅이 질어서 질퍽하게 된 곳)으로 만들었다. 

깔끔하고 세심한 FJ​의 소들은 발굽이 더러워지는 것을 매우 싫어한다. 

그 진흙 발굽을 방지하기 위해 농장주 FJ​는 목장의 진창들 위에 여러 개의 나무 판을 놓을 생각이다. 

각 나무판은 너비가 1 단위이며 다양한 길이를 갖는다.

각 나무판은​ 수직 또는 수평으로 놓여져야 한다. 

농장주 FJ​는 진창들을 덮는 데 필요한 나무판 수를 최소화하기를 원하며, 

일부 진창들을 덮는데 두 개 이상의 나무판​이 사용될 수도 있다. 

한 곳의 진창에 두 개 이상의 나무판을 포개놓을 수 있지만 나무판이 풀을 덮을 수는 없다.

FJ​가 목장의 모든 진흙을 덮는 데 필요한 최소 보드 수를 계산하십시오. 


입력형식

첫째 줄에 N, M(1≤N, M≤50)이 주어진다. 

다음 N개의 각 줄에는 M개의 문자(들)로 목장의 정보가 주어진다. 

풀은 '.'으로, 진창은 '*'로 주어진다.​ 


출력형식

FJ(농부 재우)가 사용하는 판자 수의 최소값을 출력한다.


입력 예

4 4
*.*.
.***
***.
..*.

출력 예

4

Hint!

[예제 설명]

4개의 판자를 아래와 같이 놓으면 된다.

1.2.

.333

444.

..2.

2번 판자의 일부는 3, 4번에 덮여있다.​ 




bipartite matching

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP