Candy Game

Interview

Time limit1sMemory limit128 MB

Summary

Given a colored N×N grid, determine the longest same-color run achievable in any row or column after performing exactly one swap of two adjacent different-colored cells.

Level: Medium4 of 10
Topics: Simulation, Brute force, Array
Solved: No attempts yet

Problem

An N × N board is initially filled with candies. Each cell has one candy, and the colors may differ.

The player chooses two adjacent cells with different colors and swaps the candies in those cells. After the swap, the player chooses one row or one column and eats the longest contiguous segment consisting of candies of the same color.

Given the current board, find the maximum number of candies the player can eat after exactly one swap.

Input

The first line contains the board size N, where 3 ≤ N ≤ 50.

Each of the next N lines contains the colors of the candies on the board. Red is written as C, blue as P, green as Z, and yellow as Y.

The input always contains at least one pair of adjacent cells with different colors.

Output

Print the maximum number of candies that can be eaten after one swap.

Hint

In the third visible test case, swapping the Y and C in the fourth row creates a contiguous segment of 4 candies with the same color.

Examples3

Example 1
Input
```
3
CCP
CCP
PPC
```
Expected output
```
3
```
Example 2
Input
```
4
PPPP
CYZY
CCPY
PPCC
```
Expected output
```
4
```
Example 3
Input
```
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
```
Expected output
```
4
```