시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 262 107 87 39.726%

문제

30년동안 열심히 돈을 모은 상근이는 드디어 아파트 하나를 구매했다. 상근이는 친구들을 최대한 많이 초대해 집들이를 하려고 한다.

집들이를 하기 전에 모든 사람이 앉을 수 있는 직사각형 식탁을 하나 사려고 한다. 식탁에 앉을 수 있는 사람의 수는 식탁의 둘레 길이와 같다. (네 변의 길이의 합)

상근이는 되도록 큰 식탁을 구매해서 되도록 많은 사람들과 같이 저녁을 먹을 수 있게 하려고 한다. 식탁은 항상 아파트의 변에 평행하게 놓아야 한다.

아파트의 레이아웃이 주어졌을 때, 상근이가 초대할 수 있는 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 아파트의 크기를 나타내는 R과 C가 주어진다. (1 ≤ R, C ≤ 400)

다음 R개 줄에는 C개의 문자가 주어지며, 빈 칸은 '.', 막힌 칸은 'X'로 주어진다.

상근이는 오직 빈 칸에만 식탁을 놓을 수 있다. 또, 사람의 크기는 매우 작다고 생각하면 된다.

출력

첫째 줄에 상근이가 초대할 수 있는 사람의 수를 출력한다.

예제 입력 1

2 2
..
..

예제 출력 1

7

예제 입력 2

4 4
X.XX
X..X
..X.
..XX

예제 출력 2

9

예제 입력 3

3 3
X.X
.X.
X.X

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjMwNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWI0ZTRcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPjMwXHViMTQ0XHViM2Q5XHVjNTQ4IFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWIzYzhcdWM3NDQgXHViYWE4XHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI0ZGNcdWI1MTRcdWM1YjQgXHVjNTQ0XHVkMzBjXHVkMmI4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc3NCBcdWNkMDhcdWIzMDBcdWQ1NzQgXHVjOWQxXHViNGU0XHVjNzc0XHViOTdjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzlkMVx1YjRlNFx1Yzc3NFx1Yjk3YyBcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNTQ5XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzJkZFx1ZDBjMVx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMmRkXHVkMGMxXHVjNWQwIFx1YzU0OVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWIyOTQgXHVjMmRkXHVkMGMxXHVjNzU4IFx1YjQ1OFx1YjgwOCBcdWFlMzhcdWM3NzRcdWM2NDAgXHVhYzE5XHViMmU0LiAoXHViMTI0IFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5KTxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViNDE4XHViM2M0XHViODVkIFx1ZDA3MCBcdWMyZGRcdWQwYzFcdWM3NDQgXHVhZDZjXHViOWU0XHVkNTc0XHVjMTFjIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI5Y2VcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MDBcdWIxNDFcdWM3NDQgXHViYTM5XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMmRkXHVkMGMxXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM1NDRcdWQzMGNcdWQyYjhcdWM3NTggXHViY2MwXHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YWM4YyBcdWIxOTNcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWQzMGNcdWQyYjhcdWM3NTggXHViODA4XHVjNzc0XHVjNTQ0XHVjNmMzXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWNkMDhcdWIzMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1NDRcdWQzMGNcdWQyYjhcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIsIEMgJmxlOyA0MDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBDXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YmU0OCBcdWNlNzhcdWM3NDAgJiMzOTsuJiMzOTssIFx1YjljOVx1ZDc4YyBcdWNlNzhcdWM3NDAgJiMzOTtYJiMzOTtcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjI0XHVjOWMxIFx1YmU0OCBcdWNlNzhcdWM1ZDBcdWI5Y2MgXHVjMmRkXHVkMGMxXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHViOWU0XHVjNmIwIFx1Yzc5MVx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2QwOFx1YjMwMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwNTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVE9MIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgYm91Z2h0IGFuIGFwYXJ0bWVudCBhbmQgd2FudHMgdG8gaW52aXRlIHRvIGRpbm5lciBhcyBtYW55IHBlb3BsZSBhcyBwb3NzaWJsZSB0byBjZWxlYnJhdGUgd2l0aCBoaW0uIEZvciB0aGlzIGhlIG5lZWRzIGEgbGFyZ2UgcmVjdGFuZ3VsYXIgd29vZGVuIHRhYmxlIGZvciB3aGljaCBoZSB3aWxsIHNpdCBkb3duIHdpdGggaGlzIGd1ZXN0cy4gVGhlIG51bWJlciBvZiBwZW9wbGUgYSB0YWJsZSBjYW4gYWNjb21tb2RhdGUgaXMgZXF1YWwgdG8gaXRzIHBlcmltZXRlciAodGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiBhbGwgZm91ciBzaWRlcykuIE1pcmtvIHdhbnRzIHRvIGJ1eSBhIHRhYmxlIHN1Y2ggdGhhdCBpdCBmaXRzIGluIGhpcyBhcGFydG1lbnQgYW5kIHRoYXQgYXMgbWFueSBwZW9wbGUgYXMgcG9zc2libGUgY2FuIHNpdCBkb3duIHdpdGggaGltIGZvciBkaW5uZXIuIFRoZSB0YWJsZSBtdXN0IGJlIHBsYWNlZCBzbyB0aGF0IGl0cyBlZGdlcyBhcmUgcGFyYWxsZWwgdG8gdGhlIGVkZ2VzIG9mIHRoZSBhcGFydG1lbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBsYXlvdXQgb2YgdGhlIGFwYXJ0bWVudCwgZmluZCB0aGUgbnVtYmVyIG9mIHBlb3BsZSBNaXJrbyBjYW4gaW52aXRlIHRvIGRpbm5lci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDICgxICZsZTsgUiwgUyAmbGU7IDQwMCksIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBhcGFydG1lbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIHJvd3MgY29udGFpbnMgZXhhY3RseSBTIGNoYXJhY3RlcnMgKHdpdGhvdXQgc3BhY2VzKSwgd2hldGhlciBhIHNxdWFyZSBpcyBmcmVlICgmIzM5Oy4mIzM5Oykgb3IgYmxvY2tlZCAoJiMzOTtYJiMzOTspLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBjYW4gcHV0IGhpcyB0YWJsZSBvbmx5IGluIGZyZWUgc3F1YXJlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBndWVzdHMgTWlya28gY2FuIGludml0ZSB0byBkaW5uZXIgYWZ0ZXIgaGUgYnV5cyBoaXMgdGFibGUgb24gYSBzaW5nbGUgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #2 5번