시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1731 540 323 28.014%

문제

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.

원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.

빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)

다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.

출력

첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.

예제 입력 1

5 5
.xx..
..x..
.....
...x.
...x.

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjMxMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNzVcdWM5ZDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM4MWNcdWJlNzVcdWMwYWMgXHVhZTQwXHVjNmQwXHVjNmM1XHVjNzQwIFx1YmU3NVx1YzlkMVx1Yzc0NCBcdWM2YjRcdWM2MDFcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM2ZDBcdWM2YzVcdWM3NzRcdWM3NTggXHViZTc1XHVjOWQxXHVjNzQwIFx1YWUwMFx1Yjg1Y1x1YmM4YyBcdWM3YWNcdWM4MTUgXHVjNzA0XHVhZTMwXHViOTdjIFx1ZDUzY1x1ZDU3NFx1YWMwMFx1YzljMCBcdWJhYmJcdWQ1ODhcdWFjZTAsIFx1YWNiMFx1YWQ2ZCBcdWMyZWNcdWFjMDFcdWQ1NWMgXHVjN2FjXHVjODE1IFx1YzcwNFx1YWUzMFx1YzVkMCBcdWJlNjBcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzZjNVx1Yzc3NFx1YjI5NCBcdWM5YzBcdWNkOWNcdWM3NDQgXHVjOTA0XHVjNzc0XHVhY2UwXHVjNzkwIFx1YzVlY1x1YWUzMFx1YzgwMFx1YWUzMCBcdWM5YzBcdWNkOWNcdWM3NDQgXHVjMGI0XHVkM2I0XHViY2Y0XHViMzU4IFx1YzkxMVx1YzVkMCwgXHVhYzAwXHVjMmE0XHViZTQ0XHVhYzAwIFx1YzgxY1x1Yzc3YyBcdWQwNmNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzZkMFx1YzZjNVx1Yzc3NFx1YjI5NCBcdWFkZmNcdWNjOTggXHViZTc1XHVjOWQxXHVjNzU4IFx1YWMwMFx1YzJhNFx1YWQwMFx1YzVkMCBcdWJhYjBcdWI3OTggXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU3NCBcdWQ2ZDRcdWNjZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZTc1XHVjOWQxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDAgUipDIFx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzVmNFx1Yzc0MCBcdWFkZmNcdWNjOTggXHViZTc1XHVjOWQxXHVjNzU4IFx1YWMwMFx1YzJhNFx1YWQwMFx1Yzc3NFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1Yzc0MCBcdWM2ZDBcdWM2YzVcdWM3NzRcdWM3NTggXHViZTc1XHVjOWQxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWM2YzVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjMmE0XHVhZDAwXHVhY2ZjIFx1YmU3NVx1YzlkMVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmU3NVx1YzlkMVx1YWNmYyBcdWFjMDBcdWMyYTRcdWFkMDAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWM3NFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVhYzc0XHViYjNjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWMyYTRcdWFkMDBcdWFjZmMgXHViZTc1XHVjOWQxXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkMzBjXHVjNzc0XHVkNTA0XHViNzdjXHVjNzc4XHVjNzQwIFx1Y2NhYlx1YzlmOCBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNCBcdWIzMDBcdWFjMDFcdWMxMjAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YzkxMVx1YzJlY1x1YjA3Y1x1YjlhYyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWM2YzVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjMmE0XHViOTdjIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI5Y2VcdWM3NzQgXHVkNmQ0XHVjZTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFjMDBcdWMyYTRcdWFkMDBcdWFjZmMgXHViZTc1XHVjOWQxXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI3N2NcdWM3NzhcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhY2JkXHViODVjXHViMjk0IFx1YWNiOVx1Y2U2MCBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWMxMWNcdWI4NWMgXHVjODExXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1Y2U3OFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzZjNVx1Yzc3NCBcdWJlNzVcdWM5ZDFcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzZkMFx1YzZjNVx1Yzc3NFx1YWMwMCBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWMyYTRcdWFkMDBcdWFjZmMgXHViZTc1XHVjOWQxXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI3N2NcdWM3NzhcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBSICZsZTsgMTAsMDAwLCA1ICZsZTsgQyAmbGU7IDUwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmU3NVx1YzlkMSBcdWFkZmNcdWNjOThcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTsuJiMzOTtcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc3NFx1YWNlMCwgJiMzOTt4JiMzOTtcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzc0XHViMmU0LiBcdWNjOThcdWM3NGNcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViZTQ0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmQwXHVjNmM1XHVjNzc0XHVhYzAwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjc3Y1x1Yzc3OFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlbGluZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTNweDsgd2lkdGg6MTg1cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTElOT1ZPRCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gb3ducyBhIGJha2VyeSBvbiB0aGUgZWRnZSBvZiB0aGUgY2l0eS4gQmVjYXVzZSBvZiB0aGUgZmluYW5jaWFsIGNyaXNpcywgTWlya28mIzM5O3MgbW9udGhseSBnYXMgYmlsbCBmb3IgdGhlIG92ZW5zIGhhcyBiZWNvbWUgdG9vIGxhcmdlIHNvIGhlIGRlY2lkZWQgdG8gc3RlYWwgZ2FzIGZyb20gYSBsYXJnZSBwaXBlbGluZSBuZWFyIGhpcyBiYWtlcnkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBsYW5kIHN1cnJvdW5kaW5nIHRoZSBiYWtlcnkgY2FuIGJlIG1vZGVsbGVkIGJ5IGFuIFImdGltZXM7QyBncmlkIHNvIHRoYXQgdGhlIHBpcGVsaW5lIGlzIGluIHRoZSBmaXJzdCBjb2x1bW4gYW5kIE1pcmtvJiMzOTtzIGJha2VyeSBpbiB0aGUgbGFzdCBjb2x1bW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIHdpbGwgY29ubmVjdCBwaXBlcyB0byB0aGUgZ2FzIHBpcGVsaW5lIGFuZCBoaXMgYmFrZXJ5LiBTb21lIHBhcmNlbHMgb2YgbGFuZCBhcmUgaW5hY2Nlc3NpYmxlIGFuZCBNaXJrbyBjYW5ub3QgcHV0IHBpcGVzIHRocm91Z2ggdGhlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgcGF0aCBmcm9tIHRoZSBwaXBlbGluZSB0byB0aGUgYmFrZXJ5IHN0YXJ0cyBpbiBhIGNlbGwgaW4gdGhlIGZpcnN0IGNvbHVtbiBpbiB0aGUgZ3JpZCwgZW5kcyBpbiB0aGUgbGFzdCBjb2x1bW4sIGFuZCBlYWNoIGNlbGwgb24gdGhlIHBhdGggaXMgY29ubmVjdGVkIHRvIHRoZSBjZWxsIGRpYWdvbmFsbHkgdXAtcmlnaHQsIHJpZ2h0IG9yIGRpYWdvbmFsbHkgZG93bi1yaWdodC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8gcHVsbCBhcyBtdWNoIGdhcyBmcm9tIHRoZSBwaXBlbGluZSBhcyBwb3NzaWJsZSwgTWlya28gd2FudHMgdG8gZ2V0IGFzIG1hbnkgcGF0aHMgdG8gaGlzIGJha2VyeSBhcyBwb3NzaWJsZS4gVGhlIHBhdGhzIG1heSBub3QgY3Jvc3Mgbm9yIHRvdWNoLiBJbiBvdGhlciB3b3JkcywgYXQgbW9zdCBvbmUgcGF0aCBtYXkgcGFzcyB0aHJvdWdoIGFueSBjZWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBsYXJnZXN0IG51bWJlciBvZiBwYXRocyBNaXJrbyBjYW4gcHVsbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDICgxICZsZTsgUiAmbGU7IDEwMDAwLCA1ICZsZTsgQyAmbGU7IDUwMCksIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBncmlkLkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW5zIGEgc3RyaW5nIG9mIEMgY2hhcmFjdGVycywgZWFjaCBiZWluZyBhIHBlcmlvZCAmIzM5Oy4mIzM5OyBvciB0aGUgbGV0dGVyICYjMzk7eCYjMzk7LiBUaGUgbGV0dGVyICYjMzk7eCYjMzk7IHJlcHJlc2VudHMgYW4gaW5hY2Nlc3NpYmxlIHBhcmNlbCBvZiBsYW5kLiBUaGUgZmlyc3QgYW5kIGxhc3QgY2VsbHMgaW4gZWFjaCByb3cgd2lsbCBiZSBjbGVhci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHBhdGhzIE1pcmtvIGNhbiBwdWxsIGZyb20gdGhlIHBpcGVsaW5lIHRvIHRoZSBiYWtlcnkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BpcGVsaW5lLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE1M3B4OyB3aWR0aDoxODVweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > National Competition #1 - Juniors 3번