시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB276019896644131.426%

문제

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

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

2

예제 입력 2

6 10
..x.......
.....x....
.x....x...
...x...xx.
..........
....x.....

예제 출력 2

5
W3sicHJvYmxlbV9pZCI6IjMxMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNzVcdWM5ZDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM4MWNcdWJlNzVcdWMwYWMgXHVhZTQwXHVjNmQwXHVjNmM1XHVjNzQwIFx1YmU3NVx1YzlkMVx1Yzc0NCBcdWM2YjRcdWM2MDFcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM2ZDBcdWM2YzVcdWM3NzRcdWM3NTggXHViZTc1XHVjOWQxXHVjNzQwIFx1YWUwMFx1Yjg1Y1x1YmM4YyBcdWM3YWNcdWM4MTUgXHVjNzA0XHVhZTMwXHViOTdjIFx1ZDUzY1x1ZDU3NFx1YWMwMFx1YzljMCBcdWJhYmJcdWQ1ODhcdWFjZTAsIFx1YWNiMFx1YWQ2ZCBcdWMyZWNcdWFjMDFcdWQ1NWMgXHVjN2FjXHVjODE1IFx1YzcwNFx1YWUzMFx1YzVkMCBcdWJlNjBcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzZjNVx1Yzc3NFx1YjI5NCBcdWM5YzBcdWNkOWNcdWM3NDQgXHVjOTA0XHVjNzc0XHVhY2UwXHVjNzkwIFx1YzVlY1x1YWUzMFx1YzgwMFx1YWUzMCBcdWM5YzBcdWNkOWNcdWM3NDQgXHVjMGI0XHVkM2I0XHViY2Y0XHViMzU4IFx1YzkxMVx1YzVkMCwgXHVhYzAwXHVjMmE0XHViZTQ0XHVhYzAwIFx1YzgxY1x1Yzc3YyBcdWQwNmNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzZkMFx1YzZjNVx1Yzc3NFx1YjI5NCBcdWFkZmNcdWNjOTggXHViZTc1XHVjOWQxXHVjNzU4IFx1YWMwMFx1YzJhNFx1YWQwMFx1YzVkMCBcdWJhYjBcdWI3OTggXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU3NCBcdWQ2ZDRcdWNjZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZTc1XHVjOWQxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDAgUipDIFx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzVmNFx1Yzc0MCBcdWFkZmNcdWNjOTggXHViZTc1XHVjOWQxXHVjNzU4IFx1YWMwMFx1YzJhNFx1YWQwMFx1Yzc3NFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1Yzc0MCBcdWM2ZDBcdWM2YzVcdWM3NzRcdWM3NTggXHViZTc1XHVjOWQxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWM2YzVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjMmE0XHVhZDAwXHVhY2ZjIFx1YmU3NVx1YzlkMVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmU3NVx1YzlkMVx1YWNmYyBcdWFjMDBcdWMyYTRcdWFkMDAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWM3NFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVhYzc0XHViYjNjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViOTdjIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWMyYTRcdWFkMDBcdWFjZmMgXHViZTc1XHVjOWQxXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkMzBjXHVjNzc0XHVkNTA0XHViNzdjXHVjNzc4XHVjNzQwIFx1Y2NhYlx1YzlmOCBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNCBcdWIzMDBcdWFjMDFcdWMxMjAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YzkxMVx1YzJlY1x1YjA3Y1x1YjlhYyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2ZDBcdWM2YzVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjMmE0XHViOTdjIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI5Y2VcdWM3NzQgXHVkNmQ0XHVjZTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFjMDBcdWMyYTRcdWFkMDBcdWFjZmMgXHViZTc1XHVjOWQxXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI3N2NcdWM3NzhcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhY2JkXHViODVjXHViMjk0IFx1YWNiOVx1Y2U2MCBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWMxMWNcdWI4NWMgXHVjODExXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1Y2U3OFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTQgXHVkMzBjXHVjNzc0XHVkNTA0XHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZkMFx1YzZjNVx1Yzc3NCBcdWJlNzVcdWM5ZDFcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzZkMFx1YzZjNVx1Yzc3NFx1YWMwMCBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWMyYTRcdWFkMDBcdWFjZmMgXHViZTc1XHVjOWQxXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWQzMGNcdWM3NzRcdWQ1MDRcdWI3N2NcdWM3NzhcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBSICZsZTsgMTAsMDAwLCA1ICZsZTsgQyAmbGU7IDUwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmU3NVx1YzlkMSBcdWFkZmNcdWNjOThcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTsuJiMzOTtcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc3NFx1YWNlMCwgJiMzOTt4JiMzOTtcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzc0XHViMmU0LiBcdWNjOThcdWM3NGNcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzVmNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViZTQ0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmQwXHVjNmM1XHVjNzc0XHVhYzAwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1Yjc3Y1x1Yzc3OFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUExJTk9WT0QiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIG93bnMgYSBiYWtlcnkgb24gdGhlIGVkZ2Ugb2YgdGhlIGNpdHkuIEJlY2F1c2Ugb2YgdGhlIGZpbmFuY2lhbCBjcmlzaXMsIE1pcmtvJiMzOTtzIG1vbnRobHkgZ2FzIGJpbGwgZm9yIHRoZSBvdmVucyBoYXMgYmVjb21lIHRvbyBsYXJnZSBzbyBoZSBkZWNpZGVkIHRvIHN0ZWFsIGdhcyBmcm9tIGEgbGFyZ2UgcGlwZWxpbmUgbmVhciBoaXMgYmFrZXJ5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGFuZCBzdXJyb3VuZGluZyB0aGUgYmFrZXJ5IGNhbiBiZSBtb2RlbGxlZCBieSBhbiBSJnRpbWVzO0MgZ3JpZCBzbyB0aGF0IHRoZSBwaXBlbGluZSBpcyBpbiB0aGUgZmlyc3QgY29sdW1uIGFuZCBNaXJrbyYjMzk7cyBiYWtlcnkgaW4gdGhlIGxhc3QgY29sdW1uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyB3aWxsIGNvbm5lY3QgcGlwZXMgdG8gdGhlIGdhcyBwaXBlbGluZSBhbmQgaGlzIGJha2VyeS4gU29tZSBwYXJjZWxzIG9mIGxhbmQgYXJlIGluYWNjZXNzaWJsZSBhbmQgTWlya28gY2Fubm90IHB1dCBwaXBlcyB0aHJvdWdoIHRoZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IHBhdGggZnJvbSB0aGUgcGlwZWxpbmUgdG8gdGhlIGJha2VyeSBzdGFydHMgaW4gYSBjZWxsIGluIHRoZSBmaXJzdCBjb2x1bW4gaW4gdGhlIGdyaWQsIGVuZHMgaW4gdGhlIGxhc3QgY29sdW1uLCBhbmQgZWFjaCBjZWxsIG9uIHRoZSBwYXRoIGlzIGNvbm5lY3RlZCB0byB0aGUgY2VsbCBkaWFnb25hbGx5IHVwLXJpZ2h0LCByaWdodCBvciBkaWFnb25hbGx5IGRvd24tcmlnaHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIHB1bGwgYXMgbXVjaCBnYXMgZnJvbSB0aGUgcGlwZWxpbmUgYXMgcG9zc2libGUsIE1pcmtvIHdhbnRzIHRvIGdldCBhcyBtYW55IHBhdGhzIHRvIGhpcyBiYWtlcnkgYXMgcG9zc2libGUuIFRoZSBwYXRocyBtYXkgbm90IGNyb3NzIG5vciB0b3VjaC4gSW4gb3RoZXIgd29yZHMsIGF0IG1vc3Qgb25lIHBhdGggbWF5IHBhc3MgdGhyb3VnaCBhbnkgY2VsbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcGF0aHMgTWlya28gY2FuIHB1bGwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMSAmbGU7IFIgJmxlOyAxMDAwMCwgNSAmbGU7IEMgJmxlOyA1MDApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgZ3JpZC5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgUiBsaW5lcyBjb250YWlucyBhIHN0cmluZyBvZiBDIGNoYXJhY3RlcnMsIGVhY2ggYmVpbmcgYSBwZXJpb2QgJiMzOTsuJiMzOTsgb3IgdGhlIGxldHRlciAmIzM5O3gmIzM5Oy4gVGhlIGxldHRlciAmIzM5O3gmIzM5OyByZXByZXNlbnRzIGFuIGluYWNjZXNzaWJsZSBwYXJjZWwgb2YgbGFuZC4gVGhlIGZpcnN0IGFuZCBsYXN0IGNlbGxzIGluIGVhY2ggcm93IHdpbGwgYmUgY2xlYXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsYXJnZXN0IG51bWJlciBvZiBwYXRocyBNaXJrbyBjYW4gcHVsbCBmcm9tIHRoZSBwaXBlbGluZSB0byB0aGUgYmFrZXJ5LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC85YzA3OWYwYy1hMDE2LTQyMmQtYjFkNy1iOTZjNjlmNjVhNjdcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE0MHB4OyBoZWlnaHQ6IDEyOXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5UaGUgZ3JpZCBmcm9tIHRoZSBmaXJzdCBleGFtcGxlLCBpbmNsdWRpbmcgb25lIHBvc3NpYmxlIGNvbmZpZ3VyYXRpb24gb2YgcGF0aHMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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