시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2859 858 648 31.984%

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력 1

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 1

4

힌트

4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

W3sicHJvYmxlbV9pZCI6IjMwODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWQwZDUgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNWI0XHViODM4XHVjNzQ0IFx1YzgwMVx1YzVkMCAmcXVvdDtcdWJkMDRcdWJjZjRcdWIyYzggKEJvbWJvbmkpJnF1b3Q7IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5OTBcdWFjYThcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWNjOThcdWM3NGNcdWM1ZDAgTiZ0aW1lcztOXHVkMDZjXHVhZTMwXHVjNWQwIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWNjNDRcdWM2Y2MgXHViMTkzXHViMjk0XHViMmU0LiBcdWMwYWNcdWQwZDVcdWM3NTggXHVjMGM5XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1Y2U3OFx1Yzc0NCBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVhY2UwXHViOTc4IFx1Y2U3OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWQ2NThcdWQ1NWNcdWIyZTQuJm5ic3A7XHVjNzc0XHVjODFjLCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1YzBjOVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWYwXHVjMThkIFx1YmQ4MFx1YmQ4NChcdWQ1ODkgXHViNjEwXHViMjk0IFx1YzVmNClcdWM3NDQgXHVhY2UwXHViOTc4IFx1YjJlNFx1Yzc0YyBcdWFkZjggXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWJhMzlcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1ZDBkNVx1Yzc3NCBcdWNjNDRcdWM2Y2NcdWM5YzQgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2Y0XHViNGRjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgNTApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjZjRcdWI0ZGNcdWM1ZDAgXHVjYzQ0XHVjNmNjXHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZTY4XHVhYzA0XHVjMGM5XHVjNzQwIEMsIFx1ZDMwY1x1Yjc4MFx1YzBjOVx1Yzc0MCBQLCBcdWNkMDhcdWI4NWRcdWMwYzlcdWM3NDAgWiwgXHViMTc4XHViNzgwXHVjMGM5XHVjNzQwIFlcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmEzOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+NFx1YmM4OCBcdWQ1ODlcdWM3NTggWVx1YzY0MCBDXHViOTdjIFx1YmMxNFx1YWZiOFx1YmE3NCBcdWMwYWNcdWQwZDUgXHViMTI0IFx1YWMxY1x1Yjk3YyBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCT01CT05JIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgSXZhbiBpcyBib3JlZCBhdCBtYXRoIGNsYXNzIHNvIGhlIGRlY2lkZWQgdG8gcGxheSBwb3B1bGFyIGdhbWUgY2FsbGVkICZxdW90O0JvbWJvbmkmcXVvdDsuIEF0IHRoZSBiZWdpbm5pbmcgYWxsIGZpZWxkcyBvZiBOJnRpbWVzO04gc3F1YXJlIGJvYXJkIGNvbnRhaW4gY2FuZGllcyAobm90IG5lY2Vzc2FyaWx5IG9mIHNhbWUgY29sb3IpLiBXaGVuIGl0cyBoaXMgdHVybiBwbGF5ZXIgc2hvdWxkIHN3YXAgdHdvIG5laWdoYm91cmluZyAodXAsIGRvd24sIGxlZnQgb3IgcmlnaHQpIGNhbmRpZXMgb2YgZGlmZmVyZW50IGNvbG9yIGFuZCB0aGVuIHBpY2sgc29tZSBzZXF1ZW5jZSAoaW4gcm93IG9yIGNvbHVtbikgb2Ygc2FtZSBjb2xvciBjYW5kaWVzIHdoaWNoIGhlIHdpbGwgdGFrZSBhbmQgZWF0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Jbml0aWFsIGJvYXJkIGNvbmZpZ3VyYXRpb24gaXMgZ2l2ZW4sIGhlbHAgSXZhbiBhbmQgd3JpdGUgYSBwcm9ncmFtIHdoaWNoIHdpbGwgY2FsY3VsYXRlIG1heGltYWwgbnVtYmVyIG9mIGNhbmRpZXMgaGUgY2FuIHdpbiBpbiB0aGUgZmlyc3QgbW92ZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHN0YW5kYXJkIGlucHV0IHRoZXJlIGlzIG9uZSBpbnRlZ2VyIE4gKDMgJmxlOyBOICZsZTsgNTApLCBib2FyZCBkaW1lbnNpb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBuZXh0IE4gbGluZXMgaW5pdGlhbCBib2FyZCBjb25maWd1cmF0aW9uIGlzIGdpdmVuLCBqLXRoIGNoYXJhY3RlciBpbiBpLXRoIHJvdyBkZW5vdGVzIGNvbG9yIG9mIGNhbmR5IGF0IHNxdWFyZSAoaSwgaikgOiBDIChyZWQpLCBQIChibHVlKSwgWiAoZ3JlZW4pLCBZICh5ZWxsb3cpLiBJdCB3aWxsIGFsd2F5cyBiZSBwb3NzaWJsZSB0byBtYWtlIGZpcnN0IG1vdmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygc3RhbmRhcmQgb3V0cHV0IHByaW50IHRoZSBtYXhpbWFsIG51bWJlciBvZiBjYW5kaWVzIEl2YW4gY2FuIHdpbiBpbiB0aGUgZmlyc3QgbW92ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+c3dhcHBpbmcgY2FuZGllcyBZIGFuZCBDIGluIDR0aCByb3cgSXZhbiBnZXRzIHNlcXVlbmNlIENDQ0MgaW4gZmlyc3QgY29sdW1uLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d