시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1393 888 764 67.551%

문제

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

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

꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 '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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBiNFx1YzU0NFx1YjBhOFx1YWM4YyBcdWI0MThcdWIyOTQgXHVjNTkxXHVhY2ZjIFx1YjI5MVx1YjMwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhYzAxXHVhYzAxIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJrb3plIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBjZXJ0YWluIG51bWJlciBvZiBnb2F0cyBpbiBNaWNrZXkmIzM5O3MgYmFja3lhcmQuIFdoaWxlIGhlIHdhcyBmaXJtbHkgc2xlZXBpbmcsIGh1bmdyeSB3b2x2ZXMgY2FtZSBpbiB0aGUgeWFyZCBhbmQgYXR0YWNrZWQgdGhlIGdvYXRzLjxcL3A+XHJcblxyXG48cD5ZYXJkIGlzIG9mIHJlY3Rhbmd1bGFyIHNoYXBlIGFuZCBjb25zaXN0cyBvZiBmaWVsZHMgYXJyYW5nZWQgaW4gcm93cyBhbmQgY29sdW1ucy4gQ2hhcmFjdGVyICYjMzk7LiYjMzk7IChkb3QpIGRlbm90ZXMgYW4gZW1wdHkgZmllbGQsIGNoYXJhY3RlciAmIzM5OyMmIzM5OyBkZW5vdGVzIGEgZmVuY2UsIGNoYXJhY3RlciAmIzM5O2smIzM5OyBkZW5vdGVzIGEgZ29hdCBhbmQgY2hhcmFjdGVyICYjMzk7diYjMzk7IGRlbm90ZXMgYSB3b2xmLjxcL3A+XHJcblxyXG48cD5XZSBjb25zaWRlciB0aGF0IHR3byBmaWVsZHMgYXJlIGluIHRoZSBzYW1lIHJlZ2lvbiBpZiB3ZSBjYW4gbW92ZSBmcm9tIG9uZSBmaWVsZCB0byB0aGUgb3RoZXIgYnkgYSBwYXRoIGNvbnNpc3Rpbmcgb2YgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgbW92ZXMgb25seSBhbmQgbm90IGNvbnRhaW5pbmcgYW55IGZlbmNlcy4gRmllbGRzIGZyb20gd2hpY2ggd2UgY2FuICZxdW90O2VzY2FwZSZxdW90OyBmcm9tIHRoZSB5YXJkIGFyZSBub3QgY29uc2lkZXJlZCB0byBiZSBhIHBhcnQgb2YgYW55IHJlZ2lvbi48XC9wPlxyXG5cclxuPHA+Rm9ydHVuYXRlbHksIG91ciBnb2F0cyBrbm93IGthcmF0ZSAmbmRhc2g7IHRoZXkgY2FuIGZpZ2h0IHRoZSB3b2x2ZXMgd2l0aGluIGEgcmVnaW9uIGFuZCB3aW4gKGkuZS4ga2lsbCB3b2x2ZXMpIGlmIHRoZWlyIG51bWJlciBpbiB0aGF0IHJlZ2lvbiBpcyBncmVhdGVyIHRoYW4gbnVtYmVyIG9mIHdvbHZlcyBpbiB0aGUgc2FtZSByZWdpb24uIE90aGVyd2lzZSwgd29sdmVzIGVhdCBhbGwgdGhlIGdvYXRzIGluc2lkZSB0aGF0IHJlZ2lvbi48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGJlZ2lubmluZywgYWxsIHRoZSBnb2F0cyBhbmQgd29sdmVzIGFyZSBzaXR1YXRlZCBpbnNpZGUgcmVnaW9ucyBpbiB0aGUgeWFyZC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBnb2F0cyBhbmQgdGhlIG51bWJlciBvZiB3b2x2ZXMgc3RpbGwgYWxpdmUgaW4gdGhlIG1vcm5pbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycywgUiBpIEMsIDMgJmxlOyBSLCBDICZsZTsgMjUwLCB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIHRoZSBudW1iZXIgb2YgY29sdW1ucyBvZiBNaWNrZXkmIzM5O3MgeWFyZC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIFIgbGluZXMgY29udGFpbnMgQyBjaGFyYWN0ZXJzLiBBbGwgb2YgdGhlbSB0b2dldGhlciByZXByZXNlbnQgdGhlIGxheW91dCBvZiB0aGUgeWFyZCBpLmUuIHBvc2l0aW9ucyBvZiB0aGUgZmVuY2VzLCBnb2F0cyBhbmQgd29sdmVzIGluIHRoZSB5YXJkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHR3byBudW1iZXJzLCBudW1iZXIgb2YgZ29hdHMgYW5kIG51bWJlciBvZiB3b2x2ZXMgc3RpbGwgYWxpdmUgaW4gdGhlIG1vcm5pbmcuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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