시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 473 138 118 33.146%

문제

체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이나 같은 열의 아무 위치로 이동할 수 있는 체스 말이다.

N × N 크기의 체스판에 룩을 최대한 많이 어떻게 배치할까? 라는 문제는 매우 쉽게 해결할 수 있다. 대각선으로 룩을 배치하면 된다.

문제를 좀 더 어렵게 만들어서, N x N 크기의 체스판에 폰이 몇 개 놓여있다. 이런 상황에서 룩을 최대 몇 개 배치할 수 있을까? 폰이 배치 되어 있으면, 룩은 폰에게 가로막혀 같은 열이나 같은 행의 모든 위치에 이동할 수 없다.

입력

첫 줄에 체스판의 크기 N이 주어진다. (1 ≤ N ≤ 100)

그리고 다음 N개의 줄에 체스판의 정보가 주어진다. '.'은 빈 칸을 의미하고, 'X'는 그 칸에 폰이 있음을 의미한다.

출력

주어진 체스판에 룩을 배치할 때, 최대 몇 개를 배치할 수 있는지 출력한다.

예제 입력 1

5
X....
X....
..X..
.X...
....X

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6Ijk1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4ZTkgXHViYzMwXHVjZTU4XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjYjRcdWMyYTRcdWM2NDAgXHVhZDAwXHViODI4XHViNDFjIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWNjOThcdWM3NGMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YmMzMFx1YzZiMFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjIFx1YmQ4MFx1ZDEzMCBcdWM4MTFcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNzIwXHViYTg1XHVkNTVjIFx1YmIzOFx1YzgxY1x1Yjg1Y1x1YjI5NCBOLVF1ZWVuIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWJjYzBcdWQ2MTVcdWQ1NzRcdWMxMWMgTi1Sb29rIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDtSb29rKFx1YjhlOSkmbmJzcDtcdWM3NDAgXHVjY2I0XHVjMmE0XHVjNWQwXHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWM3NzRcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzVmNFx1Yzc1OCBcdWM1NDRcdWJiMzQgXHVjNzA0XHVjZTU4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2NiNFx1YzJhNCBcdWI5ZDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk4gJnRpbWVzOyBOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDAgXHViOGU5XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YmMzMFx1Y2U1OFx1ZDU2MFx1YWU0Yz8gXHViNzdjXHViMjk0IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjMjdkXHVhYzhjIFx1ZDU3NFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHViOGU5XHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM4ODAmbmJzcDtcdWIzNTQgXHVjNWI0XHViODM1XHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNFx1YzExYywgTiB4IE4gXHVkMDZjXHVhZTMwXHVjNzU4IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWQzZjBcdWM3NzQgXHViYTg3IFx1YWMxYyBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWMwYzFcdWQ2NjlcdWM1ZDBcdWMxMWMgXHViOGU5XHVjNzQ0IFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHVhYzFjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPyBcdWQzZjBcdWM3NzQgXHViYzMwXHVjZTU4IFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YjhlOVx1Yzc0MCBcdWQzZjBcdWM1ZDBcdWFjOGMgXHVhYzAwXHViODVjXHViOWM5XHVkNjAwIFx1YWMxOVx1Yzc0MCBcdWM1ZjRcdWM3NzRcdWIwOTggXHVhYzE5XHVjNzQwIFx1ZDU4OVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4mbmJzcDsmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWFjXHVhY2UwIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTsuJiMzOTtcdWM3NDAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsICYjMzk7WCYjMzk7XHViMjk0IFx1YWRmOCBcdWNlNzhcdWM1ZDAgXHVkM2YwXHVjNzc0IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWI4ZTlcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTYwIFx1YjU0YywgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk1MjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBdHRhY2tpbmcgcm9va3MiLCJkZXNjcmlwdGlvbiI6IjxwPkNoZXNzIGluc3BpcmVkIHByb2JsZW1zIGFyZSBhIGNvbW1vbiBzb3VyY2Ugb2YgZXhlcmNpc2VzIGluIGFsZ29yaXRobXMgY2xhc3Nlcy4gU3RhcnRpbmcgd2l0aCB0aGUgd2VsbCBrbm93biA4LXF1ZWVucyBwcm9ibGVtLCBzZXZlcmFsIGdlbmVyYWxpemF0aW9ucyBhbmQgdmFyaWF0aW9ucyB3ZXJlIG1hZGUuIE9uZSBvZiB0aGVtIGlzIHRoZSBOLXJvb2tzIHByb2JsZW0sIHdoaWNoIGNvbnNpc3RzIG9mIHBsYWNpbmcgTiByb29rcyBpbiBhbiBOIGJ5IE4gY2hlc3Nib2FyZCBpbiBzdWNoIGEgd2F5IHRoYXQgdGhleSBkbyBub3QgYXR0YWNrIGVhY2ggb3RoZXIuPFwvcD5cclxuXHJcbjxwPlByb2Zlc3NvciBBbmFuZCBwcmVzZW50ZWQgdGhlIE4tcm9va3MgcHJvYmxlbSB0byBoaXMgc3R1ZGVudHMuIFNpbmNlIHJvb2tzIG9ubHkgYXR0YWNrIGVhY2ggb3RoZXIgd2hlbiB0aGV5IHNoYXJlIGEgcm93IG9yIGNvbHVtbiwgdGhleSBzb29uIGRpc2NvdmVyZWQgdGhhdCB0aGUgcHJvYmxlbSBjYW4gYmUgZWFzaWx5IHNvbHZlZCBieSBwbGFjaW5nIHRoZSByb29rcyBhbG9uZyBhIG1haW4gZGlhZ29uYWwgb2YgdGhlIGJvYXJkLiBTbywgdGhlIHByb2Zlc3NvciBkZWNpZGVkIHRvIGNvbXBsaWNhdGUgdGhlIHByb2JsZW0gYnkgYWRkaW5nIHNvbWUgcGF3bnMgdG8gdGhlIGJvYXJkLiBJbiBhIGJvYXJkIHdpdGggcGF3bnMsIHR3byByb29rcyBhdHRhY2sgZWFjaCBvdGhlciBpZiBhbmQgb25seSBpZiB0aGV5IHNoYXJlIGEgcm93IG9yIGNvbHVtbiBhbmQgdGhlcmUgaXMgbm8gcGF3biBwbGFjZWQgYmV0d2VlbiB0aGVtLiBCZXNpZGVzLCBwYXducyBvY2N1cHkgc29tZSBzcXVhcmVzLCB3aGljaCBnaXZlcyBhbiBhZGRpdGlvbmFsIHJlc3RyaWN0aW9uIG9uIHdoaWNoIHNxdWFyZXMgdGhlIHJvb2tzIG1heSBiZSBwbGFjZWQgb24uPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBzaXplIG9mIHRoZSBib2FyZCBhbmQgdGhlIGxvY2F0aW9uIG9mIHRoZSBwYXducywgdGVsbCBQcm9mZXNzb3IgQW5hbmQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvb2tzIHRoYXQgY2FuIGJlIHBsYWNlZCBvbiBlbXB0eSBzcXVhcmVzIHN1Y2ggdGhhdCBubyB0d28gb2YgdGhlbSBhdHRhY2sgZWFjaCBvdGhlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDApIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgb2YgdGhlIGJvYXJkLiBFYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBzdHJpbmcgb2YgTiBjaGFyYWN0ZXJzLiBJbiB0aGUgaS10aCBvZiB0aGVzZSBzdHJpbmdzLCB0aGUgai10aCBjaGFyYWN0ZXIgcmVwcmVzZW50cyB0aGUgc3F1YXJlIGluIHRoZSBpLXRoIHJvdyBhbmQgai10aCBjb2x1bW4gb2YgdGhlIGJvYXJkLiBUaGUgY2hhcmFjdGVyIGlzIGVpdGhlciAmbGRxdW87LiZyZHF1bzsgKGRvdCkgb3IgdGhlIHVwcGVyY2FzZSBsZXR0ZXIgJmxkcXVvO1gmcmRxdW87LCBpbmRpY2F0aW5nIHJlc3BlY3RpdmVseSBhbiBlbXB0eSBzcXVhcmUgb3IgYSBzcXVhcmUgY29udGFpbmluZyBhIHBhd24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgbGluZSB3aXRoIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBtYXhpbXVtIG51bWJlciBvZiByb29rcyB0aGF0IGNhbiBiZSBwbGFjZWQgb24gdGhlIGVtcHR5IHNxdWFyZXMgb2YgdGhlIGJvYXJkIHdpdGhvdXQgYXR0YWNraW5nIGVhY2ggb3RoZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Latin America > Latin America Regional Contests 2013 A번