시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 440 122 105 32.209%

문제

체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 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
W3sicHJvYmxlbV9pZCI6Ijk1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4ZTkgXHViYzMwXHVjZTU4XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjYjRcdWMyYTRcdWM2NDAgXHVhZDAwXHViODI4XHViNDFjIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWNjOThcdWM3NGMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YmMzMFx1YzZiMFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjIFx1YmQ4MFx1ZDEzMCBcdWM4MTFcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNzIwXHViYTg1XHVkNTVjIFx1YmIzOFx1YzgxY1x1Yjg1Y1x1YjI5NCBOLVF1ZWVuIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWJjODhcdWQ2MTVcdWQ1NzRcdWMxMWMgTi1Sb29rIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDtSb29rKFx1YjhlOSkmbmJzcDtcdWM3NDAgXHVjY2I0XHVjMmE0XHVjNWQwXHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWQ1ODlcdWM3NzRcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzVmNFx1Yzc1OCBcdWM1NDRcdWJiMzQgXHVjNzA0XHVjZTU4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2NiNFx1YzJhNCBcdWI5ZDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk4gJnRpbWVzOyBOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDAgXHViOGU5XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YmMzMFx1Y2U1OFx1ZDU2MFx1YWU0Yz8gXHViNzdjXHViMjk0IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjMjdkXHVhYzhjIFx1ZDU3NFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHViOGU5XHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM4ODAmbmJzcDtcdWIzNTQgXHVjNWI0XHViODM1XHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNFx1YzExYywgTiB4IE4gXHVkMDZjXHVhZTMwXHVjNzU4IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWQzZjBcdWM3NzQgXHViYTg3IFx1YWMxYyBcdWIxOTNcdWM1ZWNcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWMwYzFcdWQ2NjlcdWM1ZDBcdWMxMWMgXHViOGU5XHVjNzQ0IFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHVhYzFjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPyBcdWQzZjBcdWM3NzQgXHViYzMwXHVjZTU4IFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzQsIFx1YjhlOVx1Yzc0MCBcdWQzZjBcdWM1ZDBcdWFjOGMgXHVhYzAwXHViODVjXHViOWM5XHVkNjAwIFx1YWMxOVx1Yzc0MCBcdWM1ZjRcdWM3NzRcdWIwOTggXHVhYzE5XHVjNzQwIFx1ZDU4OVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4mbmJzcDsmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWFjXHVhY2UwIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTsuJiMzOTtcdWM3NDAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsICYjMzk7WCYjMzk7XHViMjk0IFx1YWRmOCBcdWNlNzhcdWM1ZDAgXHVkM2YwXHVjNzc0IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1Y2NiNFx1YzJhNFx1ZDMxMFx1YzVkMCBcdWI4ZTlcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTYwIFx1YjU0YywgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWNcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTUyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkF0dGFja2luZyByb29rcyIsImRlc2NyaXB0aW9uIjoiPHA+Q2hlc3MgaW5zcGlyZWQgcHJvYmxlbXMgYXJlIGEgY29tbW9uIHNvdXJjZSBvZiBleGVyY2lzZXMgaW4gYWxnb3JpdGhtcyBjbGFzc2VzLiBTdGFydGluZyB3aXRoIHRoZSB3ZWxsIGtub3duIDgtcXVlZW5zIHByb2JsZW0sIHNldmVyYWwgZ2VuZXJhbGl6YXRpb25zIGFuZCB2YXJpYXRpb25zIHdlcmUgbWFkZS4gT25lIG9mIHRoZW0gaXMgdGhlIE4tcm9va3MgcHJvYmxlbSwgd2hpY2ggY29uc2lzdHMgb2YgcGxhY2luZyBOIHJvb2tzIGluIGFuIE4gYnkgTiBjaGVzc2JvYXJkIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGV5IGRvIG5vdCBhdHRhY2sgZWFjaCBvdGhlci48XC9wPlxyXG5cclxuPHA+UHJvZmVzc29yIEFuYW5kIHByZXNlbnRlZCB0aGUgTi1yb29rcyBwcm9ibGVtIHRvIGhpcyBzdHVkZW50cy4gU2luY2Ugcm9va3Mgb25seSBhdHRhY2sgZWFjaCBvdGhlciB3aGVuIHRoZXkgc2hhcmUgYSByb3cgb3IgY29sdW1uLCB0aGV5IHNvb24gZGlzY292ZXJlZCB0aGF0IHRoZSBwcm9ibGVtIGNhbiBiZSBlYXNpbHkgc29sdmVkIGJ5IHBsYWNpbmcgdGhlIHJvb2tzIGFsb25nIGEgbWFpbiBkaWFnb25hbCBvZiB0aGUgYm9hcmQuIFNvLCB0aGUgcHJvZmVzc29yIGRlY2lkZWQgdG8gY29tcGxpY2F0ZSB0aGUgcHJvYmxlbSBieSBhZGRpbmcgc29tZSBwYXducyB0byB0aGUgYm9hcmQuIEluIGEgYm9hcmQgd2l0aCBwYXducywgdHdvIHJvb2tzIGF0dGFjayBlYWNoIG90aGVyIGlmIGFuZCBvbmx5IGlmIHRoZXkgc2hhcmUgYSByb3cgb3IgY29sdW1uIGFuZCB0aGVyZSBpcyBubyBwYXduIHBsYWNlZCBiZXR3ZWVuIHRoZW0uIEJlc2lkZXMsIHBhd25zIG9jY3VweSBzb21lIHNxdWFyZXMsIHdoaWNoIGdpdmVzIGFuIGFkZGl0aW9uYWwgcmVzdHJpY3Rpb24gb24gd2hpY2ggc3F1YXJlcyB0aGUgcm9va3MgbWF5IGJlIHBsYWNlZCBvbi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHNpemUgb2YgdGhlIGJvYXJkIGFuZCB0aGUgbG9jYXRpb24gb2YgdGhlIHBhd25zLCB0ZWxsIFByb2Zlc3NvciBBbmFuZCB0aGUgbWF4aW11bSBudW1iZXIgb2Ygcm9va3MgdGhhdCBjYW4gYmUgcGxhY2VkIG9uIGVtcHR5IHNxdWFyZXMgc3VjaCB0aGF0IG5vIHR3byBvZiB0aGVtIGF0dGFjayBlYWNoIG90aGVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCkgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBvZiB0aGUgYm9hcmQuIEVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyBjb250YWlucyBhIHN0cmluZyBvZiBOIGNoYXJhY3RlcnMuIEluIHRoZSBpLXRoIG9mIHRoZXNlIHN0cmluZ3MsIHRoZSBqLXRoIGNoYXJhY3RlciByZXByZXNlbnRzIHRoZSBzcXVhcmUgaW4gdGhlIGktdGggcm93IGFuZCBqLXRoIGNvbHVtbiBvZiB0aGUgYm9hcmQuIFRoZSBjaGFyYWN0ZXIgaXMgZWl0aGVyICZsZHF1bzsuJnJkcXVvOyAoZG90KSBvciB0aGUgdXBwZXJjYXNlIGxldHRlciAmbGRxdW87WCZyZHF1bzssIGluZGljYXRpbmcgcmVzcGVjdGl2ZWx5IGFuIGVtcHR5IHNxdWFyZSBvciBhIHNxdWFyZSBjb250YWluaW5nIGEgcGF3bi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBsaW5lIHdpdGggYW4gaW50ZWdlciByZXByZXNlbnRpbmcgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvb2tzIHRoYXQgY2FuIGJlIHBsYWNlZCBvbiB0aGUgZW1wdHkgc3F1YXJlcyBvZiB0aGUgYm9hcmQgd2l0aG91dCBhdHRhY2tpbmcgZWFjaCBvdGhlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=