시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 71 56 48 77.419%

문제

갤러리의 지도는 M*N의 정사각형 격자로 표현될 수 있다. 어떤 정사각형들은 벽으로 구성되어 있고, 다른 정사각형들은 빈 공간으로 구성되어 있다. 벽을 회색, 빈 공간을 흰색으로 표현하면 다음 그림과 같다.

갤러리에 그림을 걸려고 한다. 그림의 길이는 정사각형의 변의 길이의 두 배이다. 반드시 빈 공간과 인접해 있는 벽에만 그림을 걸 수 있으며, 그림들은 서로 겹칠 수 없다. 갤러리의 맵이 주어졌을 때, 최대로 걸 수 있는 그림의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1<=M, N<=1,000) 다음 M개의 줄에는 각각 N개의 문자가 주어진다. 문자는 'X' 또는 '.'이며 'X'는 벽을, '.'는 빈 공간을 나타낸다.
  입력되는 모든 데이터에서 적어도 첫 줄과 마지막 줄, 첫 열과 마지막 열은 모두 벽이다.

출력

최대 그림 개수를 출력한다.

예제 입력 1

7 10
XXXXXXXXXX
X.X.X....X
XXX.X.XX.X
XX....XX.X
X.XX..X..X
X..XX...XX
XXXXXXXXXX

예제 출력 1

14
W3sicHJvYmxlbV9pZCI6IjIxMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMjRcdWI3ZWNcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMyNFx1YjdlY1x1YjlhY1x1Yzc1OCBcdWM5YzBcdWIzYzRcdWIyOTQgTSpOXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NDAgXHViY2JkXHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NDAgXHViZTQ4IFx1YWNmNVx1YWMwNFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWJjYmRcdWM3NDQgXHVkNjhjXHVjMGM5LCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1ZDc3MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuPHA+PGltZyB3aWR0aD1cIjI4N1wiIGhlaWdodD1cIjIwM1wiIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA4XC9nYWwuUE5HXCIgXC8+PFwvcD5cclxuPHA+XHVhYzI0XHViN2VjXHViOWFjXHVjNWQwIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWFjNzhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YmNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1YjQ1MCBcdWJjMzBcdWM3NzRcdWIyZTQuIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWJlNDggXHVhY2Y1XHVhYzA0XHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NCBcdWM3ODhcdWIyOTQgXHViY2JkXHVjNWQwXHViOWNjIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWFjNzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZGY4XHViOWJjXHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFjYjlcdWNlNjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhYzI0XHViN2VjXHViOWFjXHVjNzU4IFx1YjlmNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDBcdWI4NWMgXHVhYzc4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZGY4XHViOWJjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMjRcdWI3ZWNcdWI5YWNcdWM3NTggXHVjMTM4XHViODVjIFx1YWUzOFx1Yzc3NCBNXHVhY2ZjIFx1YWMwMFx1Yjg1YyBcdWFlMzhcdWM3NzQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmx0Oz1NLCBOJmx0Oz0xLDAwMCkgXHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBOXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YjI5NCAnWCcgXHViNjEwXHViMjk0ICcuJ1x1Yzc3NFx1YmE3MCAnWCdcdWIyOTQgXHViY2JkXHVjNzQ0LCAnLidcdWIyOTQgXHViZTQ4IFx1YWNmNVx1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPGJyIFwvPlxyXG4mbmJzcDsgXHVjNzg1XHViODI1XHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM1ZDBcdWMxMWMgXHVjODAxXHVjNWI0XHViM2M0IFx1Y2NhYiBcdWM5MDRcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNCwgXHVjY2FiIFx1YzVmNFx1YWNmYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNWY0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJjYmRcdWM3NzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNkNWNcdWIzMDAgXHVhZGY4XHViOWJjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMTE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR0FMRVJJSkEiLCJkZXNjcmlwdGlvbiI6IjxwPk1hcCBvZiBhbiBhcnQgZ2FsbGVyeSBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSBzcXVhcmUgZ3JpZCBvZiBNIGNvbHVtbnMgYW5kIE4gcm93cy4gU29tZSBvZiB0aGUgc3F1YXJlcyBhcmUgd2FsbHMgd2hpbGUgb3RoZXJzIHJlcHJlc2VudHMgZW1wdHkgc3BhY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlJvb21zIGNvbnNpc3Qgb2YgYWRqYWNlbnQgZnJlZSBzcXVhcmVzIChzcXVhcmVzIHRoYXQgc2hhcmUgZWRnZSkuIE9uIHRoZSB3YWxscyBvZiB0aGUgcm9vbXMgd2Ugd2FudCB0byBoYW5nIGFzIG1hbnkgcGljdHVyZXMgYXMgcG9zc2libGUuIEV2ZXJ5IHBpY3R1cmUgb2NjdXBpZXMgZXhhY3RseSB0d28gbGVuZ3RocyBvZiBhIHNxdWFyZSBhbmQgdGhlaXIgaGVpZ2h0IGRvZXNuJnJzcXVvO3QgbWF0dGVyLiBJbiBvdGhlciB3b3JkcyB5b3UgY2FuIGhhbmcgYSBwaWN0dXJlIG9uIHRoZSB3YWxsIGlmIHRoZXJlIGFyZSB0d28gY29uc2VjdXRpdmUgd2FsbHMgYW5kIHR3byBmcmVlIHNxdWFyZXMgb3Bwb3NpdGUgb2YgdGhlbSAodGhhdCB0d28gZnJlZSBzcXVhcmVzIHNob3VsZCwgb2YgY291cnNlLCBiZSBhdCB0aGUgc2FtZSBzaWRlIG9mIHdhbGxzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY29tcHV0ZXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBpY3R1cmVzIHRoYXQgY2FuIGJlIGhhbmdlZCBvbiB0aGUgd2FsbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDhcL2dhbC5QTkdcIiBzdHlsZT1cImhlaWdodDoyMDNweDsgd2lkdGg6Mjg3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhpcyBwaWN0dXJlIHNob3dzIG9uZSBvZiB0aGUgcG9zc2libGUgc29sdXRpb25zIGZvciBhIGdhbGxlcnkgbWFwLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgdGhlcmUgYXJlIHR3byBpbnRlZ2VycyBNIGFuZCBOLCAxICZsZTsgTSxOICZsZTsgMTAwMCwgbnVtYmVyIG9mIHRoZSByb3dzIGFuZCBudW1iZXIgb2YgdGhlIGNvbHVtbnMgb2YgdGhlIGdhbGxlcnkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBuZXh0IE0gcm93cyB0aGVyZSBhcmUgTiBjaGFyYWN0ZXJzLiBFdmVyeSBjaGFyYWN0ZXIgcmVwcmVzZW50cyBlaXRoZXIgYSBmcmVlIHNxdWFyZSBvciB3YWxsLiAmbHNxdW87WCZyc3F1bzsgcmVwcmVzZW50cyB3YWxsIGFuZCAmbHNxdW87LiZyc3F1bzsgcmVwcmVzZW50cyBmcmVlIHNwYWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaXJzdCBhbmQgbGFzdCByb3csIGFzIHdlbGwgYXMgZmlyc3QgYW5kIGxhc3QgY29sdW1uIGFyZSB3YWxscy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiBmaWxlIHlvdSBzaG91bGQgd3JpdGUgbWF4aW11bSBudW1iZXIgb2YgcGljdHVyZXMgdGhhdCBjYW4gYmUgaGFuZ2VkIG9uIHdhbGxzIG9mIGdhbGxlcnk8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=