시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB193568154334.432%

문제

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI0MTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWMyZGNcdWQzMTAgXHVhZDZjXHViYTRkIFx1YjljOVx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+TiZ0aW1lcztNIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFjOGNcdWMyZGNcdWQzMTBcdWM1ZDAgXHVhZDZjXHViYTRkXHVjNzc0IFx1YjZhYlx1YjgyNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWQzZWRcdWM3NzQgMVx1Yzc3OCBcdWQxNGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YjljOVx1YzczY1x1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1ZDE0Y1x1Yzc3NFx1ZDUwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYjM0XHVkNTVjXHVkNTU4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWM5YzBcdWI5Y2MsIFx1ZDE0Y1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWIwNGFcdWM1YjRcdWIwYjRcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWQxNGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHViZDk5XHVjNzdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWFkNmNcdWJhNGRcdWM3NzQgXHViNmFiXHViODI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViZDgwXHViZDg0XHVjNzQ0IFx1YjljOVx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkMTRjXHVjNzc0XHVkNTA0XHVhYzAwIFx1ZDU1YyBcdWJjODggXHViZDk5XHVjNzQwIFx1YWNmM1x1YzVkMCBcdWQxNGNcdWM3NzRcdWQ1MDRcdWI5N2MgXHViNjEwIFx1YmQ5OVx1YzVlY1x1YjNjNCBcdWI0MWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVkMTRjXHVjNzc0XHVkNTA0XHViOTdjIFx1YmQ5OVx1Yzc3YyBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhYzAwXHViODVjXHViMDk4IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWJkOTlcdWM3NzRcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgTSgxICZsZTsgTiwgTSAmbGU7IDUwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBNXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWFjOGNcdWMyZGNcdWQzMTBcdWM3NTggXHViYWE4XHVjNTkxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWJkOTlcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFkNmNcdWJhNGRcdWM3NzQgXHVjNWM2XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc0MCAmIzM5Ozxjb2RlPi48XC9jb2RlPiYjMzk7LCBcdWFkNmNcdWJhNGRcdWM3NzQgXHVjNzg4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc0MCAmIzM5Ozxjb2RlPio8XC9jb2RlPiYjMzk7XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1Yzc3NFx1ZDUwNFx1Yjk3YyBcdWIwNGFcdWM1YjQgXHViMGI0XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI0MTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNdWRkeSBGaWVsZHMiLCJkZXNjcmlwdGlvbiI6IjxwPlJhaW4gaGFzIHB1bW1lbGVkIHRoZSBjb3dzJiMzOTsgZmllbGQsIGEgcmVjdGFuZ3VsYXIgZ3JpZCBvZiBSIHJvd3MgYW5kIEMgY29sdW1ucyAoMSAmbHQ7PSBSICZsdDs9IDUwLCAxICZsdDs9IEMgJmx0Oz0gNTApLiBXaGlsZSBnb29kIGZvciB0aGUgZ3Jhc3MsIHRoZSByYWluIG1ha2VzIHNvbWUgcGF0Y2hlcyBvZiBiYXJlIGVhcnRoIHF1aXRlIG11ZGR5LiBUaGUgY293cywgYmVpbmcgbWV0aWN1bG91cyBncmF6ZXJzLCBkb24mIzM5O3Qgd2FudCB0byBnZXQgdGhlaXIgaG9vdmVzIGRpcnR5IHdoaWxlIHRoZXkgZWF0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UbyBwcmV2ZW50IHRob3NlIG11ZGR5IGhvb3ZlcywgRmFybWVyIEpvaG4gd2lsbCBwbGFjZSBhIG51bWJlciBvZiB3b29kZW4gYm9hcmRzIG92ZXIgdGhlIG11ZGR5IHBhcnRzIG9mIHRoZSBjb3dzJiMzOTsgZmllbGQuIEVhY2ggb2YgdGhlIGJvYXJkcyBpcyAxIHVuaXQgd2lkZSwgYW5kIGNhbiBiZSBhbnkgbGVuZ3RoIGxvbmcuIEVhY2ggYm9hcmQgbXVzdCBiZSBhbGlnbmVkIHBhcmFsbGVsIHRvIG9uZSBvZiB0aGUgc2lkZXMgb2YgdGhlIGZpZWxkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiB3aXNoZXMgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBib2FyZHMgbmVlZGVkIHRvIGNvdmVyIHRoZSBtdWRkeSBzcG90cywgc29tZSBvZiB3aGljaCBtaWdodCByZXF1aXJlIG1vcmUgdGhhbiBvbmUgYm9hcmQgdG8gY292ZXIuIFRoZSBib2FyZHMgbWF5IG5vdCBjb3ZlciBhbnkgZ3Jhc3MgYW5kIGRlcHJpdmUgdGhlIGNvd3Mgb2YgZ3JhemluZyBhcmVhIGJ1dCB0aGV5IGNhbiBvdmVybGFwIGVhY2ggb3RoZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNvbXB1dGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGJvYXJkcyBGSiByZXF1aXJlcyB0byBjb3ZlciBhbGwgdGhlIG11ZCBpbiB0aGUgZmllbGQuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogUiBhbmQgQyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5SKzE6IEVhY2ggbGluZSBjb250YWlucyBhIHN0cmluZyBvZiBDIGNoYXJhY3RlcnMsIHdpdGggJiMzOTsqJiMzOTsgcmVwcmVzZW50aW5nIGEgbXVkZHkgcGF0Y2gsIGFuZCAmIzM5Oy4mIzM5OyByZXByZXNlbnRpbmcgYSBncmFzc3kgcGF0Y2guIE5vIHNwYWNlcyBhcmUgcHJlc2VudC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIGJvYXJkcyBGSiBuZWVkcy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5Cb2FyZHMgMSwgMiwgMyBhbmQgNCBhcmUgcGxhY2VkIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbjEuMi5cclxuLjMzM1xyXG40NDQuXHJcbi4uMi5cclxuPFwvcHJlPlxyXG5cclxuPHA+Qm9hcmQgMiBvdmVybGFwcyBib2FyZHMgMyBhbmQgNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=