시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB45212906244666.467%

문제

양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다.

하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.

꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있겠는가?

단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

입력

입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다.

다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.

출력

살아남게 되는 양과 늑대의 수를 각각 순서대로 출력한다.

예제 입력 1

6 6
...#..
.##v#.
#v.#.#
#.k#.#
.###.#
...###

예제 출력 1

0 2

예제 입력 2

8 8
.######.
#..k...#
#.####.#
#.#v.#.#
#.#.k#k#
#k.##..#
#.v..v.#
.######.

예제 출력 2

3 1

예제 입력 3

9 12
.###.#####..
#.kk#...#v#.
#..k#.#.#.#.
#..##k#...#.
#.#v#k###.#.
#..#v#....#.
#...v#v####.
.####.#vv.k#
.......####.

예제 출력 3

3 5
W3sicHJvYmxlbV9pZCI6IjMxODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1OTFcdWNlNThcdWFlMzAgXHVhZmNkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1OTFcdWNlNThcdWFlMzAgXHVhZmNkXHVjNzQwIFx1YjllOFx1YjBhMCBcdWIyOTFcdWIzMDBcdWFjMDAgXHViMDk4XHVkMGMwXHViMGFjXHViMmU0XHVhY2UwIFx1YjljOFx1Yzc0NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgXHVjMThkXHVjNjAwXHVjOWMwXHViOWNjIFx1Yzc3NFx1YzgyMCBcdWIzNTRcdWM3NzRcdWMwYzEgXHViOWM4XHVjNzQ0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWMxOGRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWQ2NTRcdWFjMDAgXHViMDljIFx1YWZjZFx1Yzc0MCBcdWJjZjVcdWMyMThcdWMyZWNcdWM1ZDAgXHViZDg4XHVkMGMwIFx1YzU0NFx1YzYwOCBcdWIyOTFcdWIzMDBcdWI0ZTRcdWM3NDQgXHVjNTkxXHViNGU0XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM2YjhcdWQwYzBcdWI5YWNcdWM1NDhcdWM1ZDAgXHViOWM4XHVhZDZjIFx1YzlkMVx1YzViNFx1YjEyM1x1YzViNCBcdWM1OTFcdWI0ZTRcdWM3NDQgXHVjN2ExXHVjNTQ0XHViYTM5XHVhYzhjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzU5MVx1YjRlNFx1Yzc0MCBcdWJjZjRcdWQxYjUgXHVjNTkxXHViNGU0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YzZiOFx1ZDBjMFx1YjlhYyBcdWM2MDFcdWM1ZWQgXHVjNTQ4XHVjNzU4IFx1YzU5MVx1YjRlNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViMjkxXHViMzAwXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YmNmNFx1YjJlNCZuYnNwO1x1YjM1NCBcdWI5Y2VcdWM3NDQgXHVhY2JkXHVjNmIwIFx1YjI5MVx1YjMwMFx1YWMwMCBcdWM4MDRcdWJkODAgXHVjN2ExXHVjNTQ0XHViYTM5XHVkNzhjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHVhZGY4IFx1YzY3OFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNTkxXHVjNzc0IFx1YzgwNFx1YmQ4MCBcdWM3YTFcdWM1NDRcdWJhMzlcdWQ3ODhcdWFjYTBcdWM5YzBcdWI5Y2MgXHViOWQwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFmY2RcdWM3NDAgXHVjNmNjXHViMDk5IFx1YjYxMVx1YjYxMVx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzc0XHViNGU0XHVjNzU4IFx1YWNiMFx1YWNmY1x1YjI5NCBcdWM3NzRcdWJiZjggXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHViZTQ4IFx1YWNmNVx1YWMwNFx1Yzc0NCAmIzM5Oy4mIzM5OyhcdWM4MTApXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgJiMzOTsjJiMzOTssIFx1YjI5MVx1YjMwMFx1Yjk3YyAmIzM5O3YmIzM5OywgXHVjNTkxXHVjNzQ0ICYjMzk7ayYjMzk7XHViNzdjXHVhY2UwIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNFx1YmE3NCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHViYTg3IFx1YjljOFx1YjlhY1x1Yzc1OCBcdWM1OTFcdWFjZmMgXHViMjkxXHViMzAwXHVhYzAwIFx1YzBiNFx1YzU0NFx1YjBhOFx1Yzc0NFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNhMFx1YjI5NFx1YWMwMD88XC9wPlxyXG5cclxuPHA+XHViMmU4LCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI4NWMgXHViOWM5XHVkNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWM2MDFcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVjNTkxXHVhY2ZjIFx1YjI5MVx1YjMwMFx1YWMwMCBcdWM1YzZcdWM3M2NcdWJhNzAgXHVjNTkxXHVhY2ZjIFx1YjI5MVx1YjMwMFx1YjI5NCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxJm5ic3A7XHVjNjAxXHVjNWVkXHVjNzU4IFx1YzEzOFx1Yjg1Y1x1YzY0MCBcdWFjMDBcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCZuYnNwO1x1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFIsIEMgKDMgJmxlOyBSLCBDICZsZTsgMjUwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWFjMDEgUlx1YzkwNFx1YzVkMFx1YjI5NCBDXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHVjNzc0XHViNGU0XHVjNzQwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVhZTMwXHVkNjM4XHViNGU0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBiNFx1YzU0NFx1YjBhOFx1YWM4YyBcdWI0MThcdWIyOTQgXHVjNTkxXHVhY2ZjIFx1YjI5MVx1YjMwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhYzAxXHVhYzAxIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoia296ZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgY2VydGFpbiBudW1iZXIgb2YgZ29hdHMgaW4gTWlja2V5JiMzOTtzIGJhY2t5YXJkLiBXaGlsZSBoZSB3YXMgZmlybWx5IHNsZWVwaW5nLCBodW5ncnkgd29sdmVzIGNhbWUgaW4gdGhlIHlhcmQgYW5kIGF0dGFja2VkIHRoZSBnb2F0cy48XC9wPlxyXG5cclxuPHA+WWFyZCBpcyBvZiByZWN0YW5ndWxhciBzaGFwZSBhbmQgY29uc2lzdHMgb2YgZmllbGRzIGFycmFuZ2VkIGluIHJvd3MgYW5kIGNvbHVtbnMuIENoYXJhY3RlciAmIzM5Oy4mIzM5OyAoZG90KSBkZW5vdGVzIGFuIGVtcHR5IGZpZWxkLCBjaGFyYWN0ZXIgJiMzOTsjJiMzOTsgZGVub3RlcyBhIGZlbmNlLCBjaGFyYWN0ZXIgJiMzOTtrJiMzOTsgZGVub3RlcyBhIGdvYXQgYW5kIGNoYXJhY3RlciAmIzM5O3YmIzM5OyBkZW5vdGVzIGEgd29sZi48XC9wPlxyXG5cclxuPHA+V2UgY29uc2lkZXIgdGhhdCB0d28gZmllbGRzIGFyZSBpbiB0aGUgc2FtZSByZWdpb24gaWYgd2UgY2FuIG1vdmUgZnJvbSBvbmUgZmllbGQgdG8gdGhlIG90aGVyIGJ5IGEgcGF0aCBjb25zaXN0aW5nIG9mIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIG1vdmVzIG9ubHkgYW5kIG5vdCBjb250YWluaW5nIGFueSBmZW5jZXMuIEZpZWxkcyBmcm9tIHdoaWNoIHdlIGNhbiAmcXVvdDtlc2NhcGUmcXVvdDsgZnJvbSB0aGUgeWFyZCBhcmUgbm90IGNvbnNpZGVyZWQgdG8gYmUgYSBwYXJ0IG9mIGFueSByZWdpb24uPFwvcD5cclxuXHJcbjxwPkZvcnR1bmF0ZWx5LCBvdXIgZ29hdHMga25vdyBrYXJhdGUgJm5kYXNoOyB0aGV5IGNhbiBmaWdodCB0aGUgd29sdmVzIHdpdGhpbiBhIHJlZ2lvbiBhbmQgd2luIChpLmUuIGtpbGwgd29sdmVzKSBpZiB0aGVpciBudW1iZXIgaW4gdGhhdCByZWdpb24gaXMgZ3JlYXRlciB0aGFuIG51bWJlciBvZiB3b2x2ZXMgaW4gdGhlIHNhbWUgcmVnaW9uLiBPdGhlcndpc2UsIHdvbHZlcyBlYXQgYWxsIHRoZSBnb2F0cyBpbnNpZGUgdGhhdCByZWdpb24uPFwvcD5cclxuXHJcbjxwPkluIHRoZSBiZWdpbm5pbmcsIGFsbCB0aGUgZ29hdHMgYW5kIHdvbHZlcyBhcmUgc2l0dWF0ZWQgaW5zaWRlIHJlZ2lvbnMgaW4gdGhlIHlhcmQuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgZ29hdHMgYW5kIHRoZSBudW1iZXIgb2Ygd29sdmVzIHN0aWxsIGFsaXZlIGluIHRoZSBtb3JuaW5nLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMsIFIgaSBDLCAzICZsZTsgUiwgQyAmbGU7IDI1MCwgdGhlIG51bWJlciBvZiByb3dzIGFuZCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgb2YgTWlja2V5JiMzOTtzIHlhcmQuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW5zIEMgY2hhcmFjdGVycy4gQWxsIG9mIHRoZW0gdG9nZXRoZXIgcmVwcmVzZW50IHRoZSBsYXlvdXQgb2YgdGhlIHlhcmQgaS5lLiBwb3NpdGlvbnMgb2YgdGhlIGZlbmNlcywgZ29hdHMgYW5kIHdvbHZlcyBpbiB0aGUgeWFyZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5GaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0d28gbnVtYmVycywgbnVtYmVyIG9mIGdvYXRzIGFuZCBudW1iZXIgb2Ygd29sdmVzIHN0aWxsIGFsaXZlIGluIHRoZSBtb3JuaW5nLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > Regional Competition - Seniors 3번