시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 177 33 28 22.222%

문제

R x C의 형태를 지닌 전차 안에는 의자와 사람들의 정보들이 주어진다. 사람들은 다리가 아픈 것을 매우 싫어하기 때문에 빈 의자가 보이면 무조건 앉으려고 한다.

하지만 나보다 의자에 가까이 있는 사람이 보이면, 그 사람이 먼저 앉는다는 것을 알기 때문에 양보할 수밖에 없다.

만약, 나보다 의자에 가까이 있는 사람은 없지만, 같은 거리에 있는 사람이 있으면 서로 자리를 차지하려고 할 것이므로, 그 자리는 전쟁터가 될 것이다. (심지어 모든 사람들은 싸움에 자신있기 때문에, 이러한 전쟁터를 거부하지 않는다(!) )

여러분들은 이 전차의 정보가 주어질 때, 전쟁터가 될 자리의 수를 세어주면 된다.

A행 B열에서 C행 D열과의 떨어진 거리 Dist는 다음과 같은 유클리드 거리로 계산된다.

Dist² = (A-C)² + (B-D)²

(번역 주 : 수식을 못넣어서 이렇게 표현합니다. ㅜㅜ)

입력

첫 줄에는 R과 C가 입력된다. (1 ≤ R ≤ 100) and (1 ≤ C ≤ 100)

이후 R개의 줄에 걸쳐 문자가 C개씩 주어진다. 이 문자는 '.' (빈 공간), 'X' (사람), 'L' (좌석) 만 주어지는 것이 보장된다.

'X'와 'L' 문자는 적어도 하나 이상이 주어짐이 보장되고, 하나의 'X' 문자와 같은 거리에 떨어진 'L'은 2개 이상 존재하지 않음이 보장된다.

출력

전쟁터의 수를 출력하면 된다.

예제 입력 1

4 4
.LX.
.X..
....
.L..

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjI4ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWI5YWMgXHVjODA0XHVjN2MxIiwiZGVzY3JpcHRpb24iOiI8cD5SIHggQ1x1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI5N2MgXHVjOWMwXHViMmNjIFx1YzgwNFx1Y2MyOCBcdWM1NDhcdWM1ZDBcdWIyOTQgXHVjNzU4XHVjNzkwXHVjNjQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHViMmU0XHViOWFjXHVhYzAwIFx1YzU0NFx1ZDUwOCBcdWFjODNcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAmbmJzcDtcdWJlNDggXHVjNzU4XHVjNzkwXHVhYzAwIFx1YmNmNFx1Yzc3NFx1YmE3NCBcdWJiMzRcdWM4NzBcdWFjNzQgXHVjNTQ5XHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YjA5OFx1YmNmNFx1YjJlNCBcdWM3NThcdWM3OTBcdWM1ZDAgXHVhYzAwXHVhZTRjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViY2Y0XHVjNzc0XHViYTc0LCBcdWFkZjggXHVjMGFjXHViNzhjXHVjNzc0IFx1YmEzY1x1YzgwMCBcdWM1NDlcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNTkxXHViY2Y0XHVkNTYwIFx1YzIxOFx1YmMxNlx1YzVkMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHViMDk4XHViY2Y0XHViMmU0IFx1Yzc1OFx1Yzc5MFx1YzVkMCBcdWFjMDBcdWFlNGNcdWM3NzQgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM1YzZcdWM5YzBcdWI5Y2MsIFx1YWMxOVx1Yzc0MCBcdWFjNzBcdWI5YWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjMTFjXHViODVjIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWNjMjhcdWM5YzBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YmJjMFx1Yjg1YywgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YjI5NCBcdWM4MDRcdWM3YzFcdWQxMzBcdWFjMDAgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gKFx1YzJlY1x1YzljMFx1YzViNCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YzJmOFx1YzZjMFx1YzVkMCBcdWM3OTBcdWMyZTBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjODA0XHVjN2MxXHVkMTMwXHViOTdjIFx1YWM3MFx1YmQ4MFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQoISkgKTxcL3A+XHJcblxyXG48cD48aW1nIHNyYz1cImh0dHBzOlwvXC91cy4xMjNyZi5jb21cLzQ1MHdtXC95dXBpcmFtb3NcL3l1cGlyYW1vczEyMDdcL3l1cGlyYW1vczEyMDcwMDM3M1wvMTQ0NTI1NDktJUVCJUE3JThDJUVEJTk5JTk0JUVDJTk3JTkwJUVDJTg0JTlDLSVFRCU4RiVBRCVFQiVCMCU5Qy0lRUIlOTglOTAlRUIlOEElOTQtJUVDJThCJUI4JUVDJTlCJTgwJUVDJTlEJTk4LSVFQSVCNyVCOCVFQiVBNiVCQyVFQyU5RSU4NSVFQiU4QiU4OCVFQiU4QiVBNC4tJUVCJUIyJUExJUVEJTg0JUIwLSVFQyU5RCVCQyVFQiU5RiVBQyVFQyU4QSVBNCVFRCU4QSVCOC0lRUIlQTAlODglRUMlOUQlQjQtJUVDJTg1JTk4LmpwZ1wiIHN0eWxlPVwiZm9udC1mYW1pbHk6JnF1b3Q7b3BlbiBzYW5zJnF1b3Q7LCZxdW90O2hlbHZldGljYSBuZXVlJnF1b3Q7LGhlbHZldGljYSxhcmlhbCwmcXVvdDtuYW51bSBnb3RoaWMmcXVvdDssc2Fucy1zZXJpZjsgZm9udC1zaXplOjE1cHg7IGhlaWdodDo0MDBweDsgd2lkdGg6NDUwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjXHViZDg0XHViNGU0XHVjNzQwIFx1Yzc3NCBcdWM4MDRcdWNjMjhcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YzgwNFx1YzdjMVx1ZDEzMFx1YWMwMCBcdWI0MjAgXHVjNzkwXHViOWFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWMxMzhcdWM1YjRcdWM4ZmNcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5BXHVkNTg5Jm5ic3A7Qlx1YzVmNFx1YzVkMFx1YzExYyBDXHVkNTg5IERcdWM1ZjRcdWFjZmNcdWM3NTggXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhYyBEaXN0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNzIwXHVkMDc0XHViOWFjXHViNGRjIFx1YWM3MFx1YjlhY1x1Yjg1YyZuYnNwO1x1YWNjNFx1YzBiMFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+RGlzdCZzdXAyOyA9IChBLUMpJnN1cDI7ICsgKEItRCkmc3VwMjs8XC9wPlxyXG5cclxuPHA+KFx1YmM4OFx1YzVlZCBcdWM4ZmMgOiBcdWMyMThcdWMyZGRcdWM3NDQgXHViYWJiXHViMTIzXHVjNWI0XHVjMTFjIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWQ0NWNcdWQ2MDRcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1MzE1Y1x1MzE1Yyk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgUlx1YWNmYyBDXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDsoMSAmbGU7IFIgJmxlOyAxMDApIGFuZCAoMSAmbGU7IEMgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCZuYnNwO1JcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWJiMzhcdWM3OTBcdWFjMDAgQ1x1YWMxY1x1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWIyOTQgJiMzOTsuJiMzOTsgKFx1YmU0OCBcdWFjZjVcdWFjMDQpLCAmIzM5O1gmIzM5OyAoXHVjMGFjXHViNzhjKSwgJiMzOTtMJiMzOTsgKFx1Yzg4Y1x1YzExZCkgXHViOWNjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4mIzM5O1gmIzM5O1x1YzY0MCAmIzM5O0wmIzM5OyBcdWJiMzhcdWM3OTBcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQwXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxOFx1YWNlMCwgXHVkNTU4XHViMDk4XHVjNzU4ICYjMzk7WCYjMzk7IFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhYzcwXHViOWFjXHVjNWQwIFx1YjVhOFx1YzViNFx1YzljNCAmIzM5O0wmIzM5O1x1Yzc0MCAyXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzRjXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MDRcdWM3YzFcdWQxMzBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJBS0lDRSIsImRlc2NyaXB0aW9uIjoiPHA+V2hlbiBpdCBjb21lcyB0byB0cmFtcywgYSBsb3Qgb2YgcGVvcGxlIGFyZSBjaXZpbGl6ZWQgaW5kaXZpZHVhbHMgd2hvIGtub3cgaG93IHRvIGJlaGF2ZSBpbiBvbmUuIEhvd2V2ZXIsIHRoZXJlIGFyZSBhbHdheXMgdGhvc2UgZmV3IHdobyB1cG9uIHNwb3R0aW5nIGEgcGxhY2UgdG8gc2l0IHdpbGwgcnVuIHRvd2FyZHMgaXQgaW4gc3VwZXJzb25pYyBzcGVlZHMuIElmIHRoZXkgc3BvdCBtb3JlIHRoYW4gb25lIHBsYWNlLCB0aGV5IGFsd2F5cyB0cnkgdGhlIGNsb3Nlc3Qgb25lIGZpcnN0LjxcL3A+XHJcblxyXG48cD5Qcm9ibGVtcyBhcmlzZSB3aGVuIHR3byBvciBtb3JlIHN1Y2ggaW5kaXZpZHVhbHMgYWltIGZvciB0aGUgc2FtZSBzcG90LiBJZiBvbmUgb2YgdGhlbSBpcyB0aGUgY2xvc2VzdCwgaGUgb3Igc2hlIHdpbGwgc2l0LCBhbmQgb3RoZXJzIHdvbiYjMzk7dCBldmVudCBhdHRlbXB0IHRvIG1vdmUgaW4gYW5kIGluc3RlYWQgdHVybiB0aGVpciBhdHRlbnRpb24gdG8gdGhlIG5leHQgY2xvc2VzdCBzcG90LiBJZiBob3dldmVyIHRoZXkgYXJlIGFsbCBlcXVhbGx5IGNsb3NlLCB0aGV5IHdpbGwgYWxsIHJ1biB0byB0aGUgc2VhdCByZXN1bHRpbmcgaW4gYSBtYXNzaXZlIGV4cGxvc2lvbiB0aGF0IHVzdWFsbHkgZW5kcyB3aXRoIGNvbXBsZXRlIGRlc3RydWN0aW9uIG9mIGJvdGggdGhlbSBhbmQgdGhlIHNlYXQuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBkZXNjcmlwdGlvbiBvZiBvbmUgdHJhbS4gSXQgaXMgcmVwcmVzZW50ZWQgYXMgYSB0YWJsZSB3aXRoIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBUaGUgcnVkZSBwYXNzZW5nZXJzIGFyZSBtYXJrZWQgd2l0aCB0aGUgbGV0dGVyICYjMzk7WCYjMzk7LiBFbXB0eSBzZWF0cyBhcmUgbWFya2VkIHdpdGggJiMzOTtMJiMzOTsgYW5kIHRoZSB0cmFtIGZsb29yIGlzIG1hcmtlZCB3aXRoICYjMzk7LiYjMzk7LiBOb3RlIHRoYXQgYWx0aG91Z2ggdGhlcmUgYXJlIG90aGVyIHBhc3NlbmdlcnMsIHRoZSBmb3JjZSBwcm9qZWN0ZWQgYnkgdGhlc2UgaWRpb3RzIGlzIG1vcmUgdGhhbiBlbm91Z2ggdG8gc2ltcGx5IHdhbGsgdGhyb3VnaCB0aGVtLjxcL3A+XHJcblxyXG48cD5EaXN0YW5jZSBiZXR3ZWVuIHR3byBjZWxscyBpcyB0aGUgRXVjbGlkIGRpc3RhbmNlIGJldHdlZW4gdGhlaXIgY2VudGVycy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiBleHBsb3Npb25zIHdoaWNoIHdpbGwgdGFrZSBwbGFjZSBiZWZvcmUgYWxsIHBlb3BsZSBhcmUgc2VhdGVkLCBvciBkZXN0cm95ZWQsIG9yIHRoZXkgcnVuIG91dCBvZiBjaGFpcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMsIFIgKDEgJmxlOyBSICZsZTsgMTAwKSBhbmQgQyAoMSAmbGU7IEMgJmxlOyAxMDApLCBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucy48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgUiBsaW5lcyBjb250YWluIEMgY2hhcmFjdGVycyBlYWNoLiAmIzM5Oy4mIzM5OywgJiMzOTtYJiMzOTsgb3IgJiMzOTtMJiMzOTsuPFwvcD5cclxuXHJcbjxwPlRoZXJlIHdpbGwgYWx3YXlzIGJlIGF0IGxlYXN0IG9uZSBjaGFyYWN0ZXIgJiMzOTtYJiMzOTsgYW5kIGF0IGxlYXN0IG9uZSAmIzM5O0wmIzM5OyBpbiB0aGUgaW5wdXQuIEFsc28sIHRoZXJlIHdpbGwgYmUgbm8gdHdvICYjMzk7TCYjMzk7IGNoYXJhY3RlcnMgc3VjaCB0aGF0IHRoZXkgYXJlIGJvdGggZXF1YWxseSBkaXN0YW50IHRvIHNvbWUgJiMzOTtYJiMzOTsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBleHBsb3Npb24gZm9yIHRoZSBnaXZlbiBsYXlvdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d