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

문제

상범이와 영훈이는 체스를 변형한 새롭고 참신하며 혁신적인 게임을 개발했다. 이 게임은 R행 C열의 체스판에서 플레이되는 게임이다. 각 플레이어는 몇개의 체스 킹 말을 가지고 시작한다. 체스 킹은 상하좌우 대각선 총 8방향으로 한 칸씩 이동할 수 있다.

이 게임의 가장 독특한 점은 점수 계산 방법이다. 상범이가 만든 게임인지라 역시 기괴함을 자랑하는데, 각 플레이어의 모든 두 킹 간의 최단 거리의 합이 점수가 된다. 이때 두 말 사이의 최단 거리는 한 킹이 다른 킹의 위치까지 이동하기 위해 필요한 이동의 횟수이다. 이때, 이러한 이동 경로 위에 다른 말이 있어도 무시하고 최단 거리를 계산해야 한다.

현재 게임 판의 상태가 주어졌을 때, 상범이와 영훈이의 점수를 구해보자.

입력

첫 번째 줄에는 행의 수 R과 열의 수 C가 주어진다(1 ≤ R, C ≤ 1,000).

다음 R개의 줄에는 C개의 문자가 주어지는데, 'M'은 상범이의 킹, 'S'는 영훈이의 킹, 그리고 '.'은 빈 칸을 이야기한다.

체스판에는 상범이와 영훈이의 말이 최소한 하나씩은 존재한다.

출력

첫 번째 줄에 상범이와 영훈이의 점수를 공백으로 구분하여 출력한다.

예제 입력 1

2 3
SMS
MMS

예제 출력 1

3 5
W3sicHJvYmxlbV9pZCI6IjI4ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWJjOTQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWJjOTRcdWM3NzRcdWM2NDAgXHVjNjAxXHVkNmM4XHVjNzc0XHViMjk0IFx1Y2NiNFx1YzJhNFx1Yjk3YyBcdWJjYzBcdWQ2MTVcdWQ1NWMgXHVjMGM4XHViODZkXHVhY2UwIFx1Y2MzOFx1YzJlMFx1ZDU1OFx1YmE3MCBcdWQ2MDFcdWMyZTBcdWM4MDFcdWM3NzggXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBSXHVkNTg5IENcdWM1ZjRcdWM3NTggXHVjY2I0XHVjMmE0XHVkMzEwXHVjNWQwXHVjMTFjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YjQxOFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHViYTg3XHVhYzFjXHVjNzU4IFx1Y2NiNFx1YzJhNCBcdWQwYjkgXHViOWQwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1Y2NiNFx1YzJhNCBcdWQwYjlcdWM3NDAgXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwJm5ic3A7XHViMzAwXHVhYzAxXHVjMTIwIFx1Y2QxZCZuYnNwOzhcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OFx1YzUyOSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHViM2M1XHVkMmI5XHVkNTVjIFx1YzgxMFx1Yzc0MCBcdWM4MTBcdWMyMTggXHVhY2M0XHVjMGIwIFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC4mbmJzcDtcdWMwYzFcdWJjOTRcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YWM4Y1x1Yzc4NFx1Yzc3OFx1YzljMFx1Yjc3YyBcdWM1ZWRcdWMyZGMgXHVhZTMwXHVhZDM0XHVkNTY4XHVjNzQ0IFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVhYzAxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViNDUwJm5ic3A7XHVkMGI5Jm5ic3A7XHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWI0NTAgXHViOWQwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjXHViMjk0IFx1ZDU1YyBcdWQwYjlcdWM3NzQgXHViMmU0XHViOTc4IFx1ZDBiOVx1Yzc1OCBcdWM3MDRcdWNlNThcdWFlNGNcdWM5YzAmbmJzcDtcdWM3NzRcdWIzZDlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3NzRcdWIzZDlcdWM3NTggXHVkNjlmXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMsJm5ic3A7XHVjNzc0XHViN2VjXHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWFjYmRcdWI4NWMgXHVjNzA0XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWI5ZDBcdWM3NzQgXHVjNzg4XHVjNWI0XHViM2M0IFx1YmIzNFx1YzJkY1x1ZDU1OFx1YWNlMCBcdWNkNWNcdWIyZTggXHVhYzcwXHViOWFjXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWFjOGNcdWM3ODQgXHVkMzEwXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM2NDAgXHVjNjAxXHVkNmM4XHVjNzc0XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1ODlcdWM3NTggXHVjMjE4IFJcdWFjZmMgXHVjNWY0XHVjNzU4IFx1YzIxOCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgxICZsZTsgUiwgQyAmbGU7IDEsMDAwKS48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjJm5ic3A7Ulx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgQ1x1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCAmIzM5O00mIzM5O1x1Yzc0MCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM3NTggXHVkMGI5LCAmIzM5O1MmIzM5O1x1YjI5NCBcdWM2MDFcdWQ2YzhcdWM3NzRcdWM3NTggXHVkMGI5LCBcdWFkZjhcdWI5YWNcdWFjZTAgJiMzOTsuJiMzOTtcdWM3NDAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWM3NzRcdWM1N2NcdWFlMzBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMFx1YjI5NCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM2NDAgXHVjNjAxXHVkNmM4XHVjNzc0XHVjNzU4IFx1YjlkMFx1Yzc3NCBcdWNkNWNcdWMxOGNcdWQ1NWMgXHVkNTU4XHViMDk4XHVjNTI5XHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWJjOTRcdWM3NzRcdWM2NDAgXHVjNjAxXHVkNmM4XHVjNzc0XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1JBTEpFVkkiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGFuZCBTbGF2a28gYXJlIHBsYXlpbmcgYSBjaGVzcyBsaWtlIGdhbWUuIFRoZSBnYW1lIGlzIHBsYXllZCBvbiBhIG5vbi1zdGFuZGFyZCBjaGVzcyBib2FyZCBzaXplZCBSIHJvd3MgYnkgQyBjb2x1bW5zLiBFYWNoIHBsYXllciBzdGFydHMgd2l0aCBzb21lIG51bWJlciBvZiBjaGVzcyBraW5ncy4gSW4gY2hlc3Mga2luZ3MgY2FuIG1vdmUgZnJvbSB0aGVpciBjdXJyZW50IGZpZWxkIHRvIGFueSBvZiB0aGUgOCBuZWlnaGJvdXJpbmcgZmllbGRzLjxcL3A+XHJcblxyXG48cD5QbGF5ZXIgc3ByZWFkIGlzIGRlZmluZWQgYXMgdGhlIGNvbXBsZXRlIHN1bSBvZiBkaXN0YW5jZXMgYmV0d2VlbiBhbGwgcGFpcnMgb2YgcGllY2VzIG9mIHRoZSBnaXZlbiBwbGF5ZXIuIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBwaWVjZXMgaXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBtb3ZlcyByZXF1aXJlZCBmb3IgYm90aCBwaWVjZXMgdG8gcmVhY2ggdGhlIHNhbWUgZmllbGQuIE5vIGFjdHVhbCBtb3ZlcyBhcmUgcGVyZm9ybWVkIHdoZW4gY2FsY3VsYXRpbmcgdGhlIGRpc3RhbmNlIGFuZCBhcyBzdWNoIGVuZW15IHBpZWNlcyBkbyBub3QgaW5mbHVlbmNlIHRoZSByZXN1bHQuPFwvcD5cclxuXHJcbjxwPk1pcmtvIGtub3dzIHRoYXQgdGhlIHNwcmVhZCBpcyBhIHZpdGFsIHBpZWNlIG9mIHN0cmF0ZWdpYyBpbmZvcm1hdGlvbiBhbmQgd291bGQgbGlrZSB5b3UgdG8gbWFrZSBoaW0gYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgYm90aCBoaXMgYW5kIFNsYXZrbyYjMzk7cyBzcHJlYWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMSAmbGU7IFIsIEMgJmxlOyAxIDAwMCksIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zLjxcL3A+XHJcblxyXG48cD5OZXh0IFIgbGluZXMgY29udGFpbiBDIGNoYXJhY3RlcnMgZWFjaC4gQ2hhcmFjdGVyICYjMzk7TSYjMzk7IGRlbm90ZXMgTWlya28mIzM5O3MgcGllY2UsICYjMzk7UyYjMzk7IFNsYXZrbyYjMzk7cyBwaWVjZSBhbmQgJiMzOTsuJiMzOTsgZGVub3RlcyBhbiBlbXB0eSBmaWVsZC48XC9wPlxyXG5cclxuPHA+VGhlcmUgaXMgYXQgbGVhc3Qgb25lIHBpZWNlIHBlciBwbGF5ZXIgb24gdGhlIGJvYXJkLiBPdGhlcndpc2UgdGhlIGdhbWUgd291bGQgYmUgb3Zlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgeW91IG5lZWQgdG8gcHJpbnQgZXhhY3RseSB0d28gaW50ZWdlcnMuIFRoZSBmaXJzdCBpbnRlZ2VycyBpcyB0aGUgc3ByZWFkIG9mIE1pcmtvJiMzOTtzIGFuZCB0aGUgc2Vjb25kIFNsYXZrbyYjMzk7cyBwaWVjZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #7 5번