시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 747 278 212 36.806%

문제

N×M 모양의 게시판에 구멍이 뚫려 있다. 이를 폭이 1인 테이프를 이용하여 막으려 한다. 테이프의 길이는 무한하다고 생각해도 좋지만, 테이프를 끊어내는 횟수를 최소로 하려 한다. 테이프를 붙일 때에는 구멍이 뚫려 있지 않은 부분을 막아서는 안 된다. 하지만 테이프가 한 번 붙은 곳에 테이프를 또 붙여도 된다. 또한, 테이프를 붙일 때에는 가로나 세로로 붙이는 경우만 허용한다.

입력

첫째 줄에 N, M(1≤N, M≤50)이 주어진다. 다음 N개의 줄에는 M개의 문자로 게시판의 모양이 주어진다. 각각의 문자는 붙어 있으며, 구멍이 없는 부분은 '.', 구멍이 있는 부분은 '*'으로 주어진다.  

출력

첫째 줄에 테이프를 끊어 내는 횟수의 최솟값을 출력한다.

예제 입력 1

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

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI0MTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWMyZGNcdWQzMTAgXHVhZDZjXHViYTRkIFx1YjljOVx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+TiZ0aW1lcztNIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFjOGNcdWMyZGNcdWQzMTBcdWM1ZDAgXHVhZDZjXHViYTRkXHVjNzc0IFx1YjZhYlx1YjgyNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWQzZWRcdWM3NzQgMVx1Yzc3OCBcdWQxNGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YjljOVx1YzczY1x1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1ZDE0Y1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTU4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWM5YzBcdWI5Y2MsIFx1ZDE0Y1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWIwNGFcdWM1YjRcdWIwYjRcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWQxNGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHViZDk5XHVjNzdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWFkNmNcdWJhNGRcdWM3NzQgXHViNmFiXHViODI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViZDgwXHViZDg0XHVjNzQ0IFx1YjljOVx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkMTRjXHVjNzc0XHVkNTA0XHVhYzAwIFx1ZDU1YyBcdWJjODggXHViZDk5XHVjNzQwIFx1YWNmM1x1YzVkMCBcdWQxNGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHViNjEwIFx1YmQ5OVx1YzVlY1x1YjNjNCBcdWI0MWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVkMTRjXHVjNzc0XHVkNTA0XHViOTdjIFx1YmQ5OVx1Yzc3YyBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhYzAwXHViODVjXHViMDk4IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSgxJmxlO04sIE0mbGU7NTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViODVjIFx1YWM4Y1x1YzJkY1x1ZDMxMFx1Yzc1OCBcdWJhYThcdWM1OTFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYjM4XHVjNzkwXHViMjk0IFx1YmQ5OVx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWQ2Y1x1YmE0ZFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHViZDgwXHViZDg0XHVjNzQwICcuJywgXHVhZDZjXHViYTRkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NDAgJyonXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJm5ic3A7PFwvcD5cclxuPHA+PFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWIwNGFcdWM1YjQgXHViMGI0XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11ZGR5IEZpZWxkcyIsImRlc2NyaXB0aW9uIjoiPHA+UmFpbiBoYXMgcHVtbWVsZWQgdGhlIGNvd3MmIzM5OyBmaWVsZCwgYSByZWN0YW5ndWxhciBncmlkIG9mIFIgcm93cyBhbmQgQyBjb2x1bW5zICgxICZsdDs9IFIgJmx0Oz0gNTAsIDEgJmx0Oz0gQyAmbHQ7PSA1MCkuIFdoaWxlIGdvb2QgZm9yIHRoZSBncmFzcywgdGhlIHJhaW4gbWFrZXMgc29tZSBwYXRjaGVzIG9mIGJhcmUgZWFydGggcXVpdGUgbXVkZHkuIFRoZSBjb3dzLCBiZWluZyBtZXRpY3Vsb3VzIGdyYXplcnMsIGRvbiYjMzk7dCB3YW50IHRvIGdldCB0aGVpciBob292ZXMgZGlydHkgd2hpbGUgdGhleSBlYXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRvIHByZXZlbnQgdGhvc2UgbXVkZHkgaG9vdmVzLCBGYXJtZXIgSm9obiB3aWxsIHBsYWNlIGEgbnVtYmVyIG9mIHdvb2RlbiBib2FyZHMgb3ZlciB0aGUgbXVkZHkgcGFydHMgb2YgdGhlIGNvd3MmIzM5OyBmaWVsZC4gRWFjaCBvZiB0aGUgYm9hcmRzIGlzIDEgdW5pdCB3aWRlLCBhbmQgY2FuIGJlIGFueSBsZW5ndGggbG9uZy4gRWFjaCBib2FyZCBtdXN0IGJlIGFsaWduZWQgcGFyYWxsZWwgdG8gb25lIG9mIHRoZSBzaWRlcyBvZiB0aGUgZmllbGQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIHdpc2hlcyB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIGJvYXJkcyBuZWVkZWQgdG8gY292ZXIgdGhlIG11ZGR5IHNwb3RzLCBzb21lIG9mIHdoaWNoIG1pZ2h0IHJlcXVpcmUgbW9yZSB0aGFuIG9uZSBib2FyZCB0byBjb3Zlci4gVGhlIGJvYXJkcyBtYXkgbm90IGNvdmVyIGFueSBncmFzcyBhbmQgZGVwcml2ZSB0aGUgY293cyBvZiBncmF6aW5nIGFyZWEgYnV0IHRoZXkgY2FuIG92ZXJsYXAgZWFjaCBvdGhlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q29tcHV0ZSB0aGUgbWluaW11bSBudW1iZXIgb2YgYm9hcmRzIEZKIHJlcXVpcmVzIHRvIGNvdmVyIGFsbCB0aGUgbXVkIGluIHRoZSBmaWVsZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBSIGFuZCBDJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uUisxOiBFYWNoIGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgQyBjaGFyYWN0ZXJzLCB3aXRoICYjMzk7KiYjMzk7IHJlcHJlc2VudGluZyBhIG11ZGR5IHBhdGNoLCBhbmQgJiMzOTsuJiMzOTsgcmVwcmVzZW50aW5nIGEgZ3Jhc3N5IHBhdGNoLiBObyBzcGFjZXMgYXJlIHByZXNlbnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgYm9hcmRzIEZKIG5lZWRzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Qm9hcmRzIDEsIDIsIDMgYW5kIDQgYXJlIHBsYWNlZCBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG4xLjIuXHJcbi4zMzNcclxuNDQ0LlxyXG4uLjIuXHJcbjxcL3ByZT5cclxuXHJcbjxwPkJvYXJkIDIgb3ZlcmxhcHMgYm9hcmRzIDMgYW5kIDQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=