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

문제

로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다.

성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉을 수 있다. 성당의 좌석 배치는 크기가 R × S인 행렬로 나타낼 수 있고, 행렬의 각 원소는 사람이 있는지 없는지로 나타낼 수 있다. 모든 사람은 자신의 이웃과 악수를 한다고 가정한다. 이웃은 사람이 있는 칸과 인접한 칸 여덟개이다. (칸이 존재하지 않을 수도 있다)

상근이는 오늘도 늦잠을 자 미사에 늦었고, 가장 좋아하는 평화 의식 시간을 참여하기 위해 성당 입구까지 달려왔다. 상근이는 최대한 많은 사람과 악수를 할 수 있는 자리에 앉으려고 한다. 만약, 남은 자리가 없는 경우에는 상근이는 저녁 미사에 다시 참가하려고 한다. 또, 상근이보다 지각하는 사람은 없다.

상근이가 들어가기 바로 전 성당에 앉아있는 사람의 배치가 주어진다. 평화 의식이 진행되는 동안 총 몇 번의 악수가 행해지는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 S가 주어진다. (1 ≤ R, S ≤ 50)

다음 R개 줄에는 S개의 문자가 주어진다. 이 R × S 개의 문자는 성당에 자리 배치를 나타낸다. '.'은 빈 자리, 'o'는 사람이 앉아있는 자리이다.

출력

평화 의식에서 총 몇 번의 악수가 행해지는지 출력한다.

예제 입력 1

2 3
..o
o..

예제 출력 1

2

예제 입력 2

2 2
oo
oo

예제 출력 2

6
W3sicHJvYmxlbV9pZCI6Ijk1MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWI5YzggXHVjZTc0XHVkMWE4XHViOWFkIFx1YmJmOFx1YzBhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViODVjXHViOWM4IFx1Y2U3NFx1ZDFhOFx1YjlhZCBcdWJiZjhcdWMwYWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YmE0Ylx1YzljNCBcdWJkODBcdWJkODRcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM1NDVcdWMyMThcdWI5N2MgXHVkNTU4XHViYTc0XHVjMTFjICZxdW90O1x1ZDNjOVx1ZDY1NFx1YWMwMCBcdWQ1NjhcdWFlZDhcdWQ1NThcdWFlMzBcdWI5N2MmcXVvdDsgXHVjNzc0XHViNzdjXHVhY2UwIFx1YjlkMFx1ZDU1OFx1YjI5NCBcdWQzYzlcdWQ2NTQgXHVjNzU4XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzFcdWIyZjlcdWM1ZDBcdWIyOTQgUlx1YWMxY1x1Yzc1OCBcdWJjYTRcdWNlNThcdWFjMDAgXHVkNTVjIFx1ZDU4OVx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViY2E0XHVjZTU4XHVjNWQwXHViMjk0IFx1Y2QxZCBTXHViYTg1XHVjNzc0IFx1YzU0OVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMxMzFcdWIyZjlcdWM3NTggXHVjODhjXHVjMTFkIFx1YmMzMFx1Y2U1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWFjMDAgUiAmdGltZXM7IFNcdWM3NzggXHVkNTg5XHViODJjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzc0XHVjNmMzXHVhY2ZjIFx1YzU0NVx1YzIxOFx1Yjk3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWM2YzNcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OCBcdWM1ZWNcdWIzNWZcdWFjMWNcdWM3NzRcdWIyZTQuIChcdWNlNzhcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0KTxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzU5YzQ4ZGY2LTA5MmYtNDFiNC04N2YzLTQzMDQ0ODdiNDNiOFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTAwcHg7IGhlaWdodDogOTJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzYyNFx1YjI5OFx1YjNjNCBcdWIyYTZcdWM3YTBcdWM3NDQgXHVjNzkwIFx1YmJmOFx1YzBhY1x1YzVkMCBcdWIyYTZcdWM1YzhcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVkM2M5XHVkNjU0IFx1Yzc1OFx1YzJkZCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjYzM4XHVjNWVjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxMzFcdWIyZjkgXHVjNzg1XHVhZDZjXHVhZTRjXHVjOWMwIFx1YjJlY1x1YjgyNFx1YzY1NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjMGFjXHViNzhjXHVhY2ZjIFx1YzU0NVx1YzIxOFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNTQ5XHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWIwYThcdWM3NDAgXHVjNzkwXHViOWFjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgwMFx1YjE0MSBcdWJiZjhcdWMwYWNcdWM1ZDAgXHViMmU0XHVjMmRjIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViY2Y0XHViMmU0IFx1YzljMFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViNGU0XHVjNWI0XHVhYzAwXHVhZTMwIFx1YmMxNFx1Yjg1YyBcdWM4MDQgXHVjMTMxXHViMmY5XHVjNWQwIFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzMwXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkM2M5XHVkNjU0IFx1Yzc1OFx1YzJkZFx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1Y2QxZCBcdWJhODcgXHViYzg4XHVjNzU4IFx1YzU0NVx1YzIxOFx1YWMwMCBcdWQ1ODlcdWQ1NzRcdWM5YzBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFJcdWFjZmMgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUiwgUyAmbGU7IDUwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgUlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgU1x1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgUiAmdGltZXM7IFMgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWMxMzFcdWIyZjlcdWM1ZDAgXHVjNzkwXHViOWFjIFx1YmMzMFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuICYjMzk7LiYjMzk7XHVjNzQwIFx1YmU0OCBcdWM3OTBcdWI5YWMsICYjMzk7byYjMzk7XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1NDlcdWM1NDRcdWM3ODhcdWIyOTQgXHVjNzkwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDNjOVx1ZDY1NCBcdWM3NThcdWMyZGRcdWM1ZDBcdWMxMWMgXHVjZDFkIFx1YmE4NyBcdWJjODhcdWM3NTggXHVjNTQ1XHVjMjE4XHVhYzAwIFx1ZDU4OVx1ZDU3NFx1YzljMFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTUxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1JU0EiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbmljZSBwYXJ0IG9mIHRoZSBSb21hbiBDYXRob2xpYyBNYXNzIGlzIHRoZSByaXRlIG9mIHBlYWNlIHdoZW4gcGVvcGxlIHNoYWtlIGhhbmRzIHdpdGggdGhlaXIgbmVpZ2hib3VycyBhbmQgc2F5ICZxdW90O3BlYWNlIGJlIHdpdGggeW91JnF1b3Q7LiBNaXJrbyBoYXMgZm91bmQgYSB3YXkgdG8gdHVybiB0aGlzIHJpdHVhbCBpbnRvIGhpcyBvd24gZmF2b3IuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluc2lkZSB0aGUgY2h1cmNoLCB0aGVyZSBhcmUgUiByb3dzIG9mIGJlbmNoZXMgd2hlcmUgZWFjaCByb3cgY2FuIGhvbGQgYSBjYXBhY2l0eSBvZiBTIHBlb3BsZS4gV2UgY2FuIGltYWdpbmUgdGhlIHNlYXRpbmcgb3JkZXIgYXMgYSBtYXRyaXggc2l6ZWQgUiB4IFMgd2hlcmUgZWFjaCBlbGVtZW50IHJlcHJlc2VudHMgZWl0aGVyIGEgcGVyc29uIG9yIGFuIGVtcHR5IHNlYXRpbmcgc3BhY2UuIExldCB1cyBhc3N1bWUgdGhhdCBlYWNoIHBlcnNvbiBzaGFrZXMgaGFuZHMgd2l0aCB0aGVpciBuZWlnaGJvdXJzLiBUaGF0IG1lYW5zIHRoYXQgdGhlIG5laWdoYm91cnMgYXJlIGxvY2F0ZWQgaW4gb25lIG9mIHRoZSBlaWdodCBuZWlnaGJvdXJpbmcgZWxlbWVudHMgKGlmIHN1Y2ggZWxlbWVudCBleGlzdHMpOiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzU5YzQ4ZGY2LTA5MmYtNDFiNC04N2YzLTQzMDQ0ODdiNDNiOFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTAwcHg7IGhlaWdodDogOTJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+QSBzZWF0aW5nIG9yZGVyIG9mIHRoZSBwZW9wbGUgaW5zaWRlIHRoZSBjaHVyY2ggaGFzIGJlZW4gZ2l2ZW4gYmVmb3JlIE1pcmtvIGVudGVycy4gTWlya28gaXMsIG9mIGNvdXJzZSwgbGF0ZSBmb3IgdGhlIG1vcm5pbmcgTWFzcyBhbmQgd2lsbCBzaXQgaW4gYW4gZW1wdHkgc3BhY2Ugc28gdGhhdCBoZSBzaGFrZXMgaGFuZHMgd2l0aCBhcyBtYW55IHBlb3BsZSBhcyBoZSBjYW4uIElmIHRoZXJlIGFyZSBubyBlbXB0eSBzZWF0cyBsZWZ0LCBNaXJrbyB3aWxsIHNpbXBseSBnaXZlIHVwIG9uIHRoZSBpZGVhIGFuZCBnbyB0byB0aGUgZXZlbmluZyBNYXNzIGluc3RlYWQuIFdlIGNhbiBhc3N1bWUgdGhhdCBub2JvZHkgZW50ZXJzIHRoZSBjaHVyY2ggYWZ0ZXIgTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkNhbGN1bGF0ZSB0aGUgdG90YWwgbnVtYmVyIG9mIGhhbmRzaGFrZXMgZ2l2ZW4gZHVyaW5nIHRoZSBtb3JuaW5nIE1hc3MuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBwb3NpdGl2ZSBpbnRlZ2VycyBSIGFuZCBTICgxICZsZTsgUiwgUyAmbGU7IDUwKSBhcyBzdGF0ZWQgaW4gdGhlIHRleHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW5zIFMgY2hhcmFjdGVycy4gVGhlc2UgUiB4IFMgY2hhcmFjdGVycyByZXByZXNlbnQgdGhlIHNlYXRpbmcgb3JkZXIuIFRoZSBjaGFyYWN0ZXIgJiMzOTsuJiMzOTsgKGRvdCkgcmVwcmVzZW50cyBhbiBlbXB0eSBwbGFjZSBhbmQgdGhlIGNoYXJhY3RlciAmIzM5O28mIzM5OyAobG93ZXJjYXNlIGxldHRlciBvKSByZXByZXNlbnRzIGEgcGVyc29uLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIGhhbmRzaGFrZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBmaXJzdCBleGFtcGxlOiBNaXJrbyB3aWxsIHNpdCBpbiBhIHdheSB0aGF0IGhlIGNhbiBzaGFrZSBoYW5kcyB3aXRoIGJvdGggcGVyc29ucywgd2hpY2ggZ2l2ZXMgdXMgdHdvIHBvc3NpYmlsaXRpZXM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbi5vbyAuLm9cclxuby4uIG9vLjxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #2 2번