Shortest Path with Same Color Constraint

You are given a grid with n rows. Each row is represented by a string containing characters. The grid represents cells with different colors (each color is represented by a character), and a dot . represents an impassable cell.

Your task is to determine the shortest path from the top-left cell (position (0,0)) to the bottom-right cell (position (n-1, m-1)), moving only in the four cardinal directions (up, down, left, right). You are allowed to move only to a neighboring cell that has exactly the same color as the current cell.

Note: If the starting cell or the destination cell is impassable (i.e. a dot), then no valid path exists. Additionally, if no path exists given the constraints, output \(-1\).

For example, consider a grid of size \(3\times3\):

a.a
aaa
a.a

The shortest path from (0,0) to (2,2) in which all moves are on cells of the same color has 4 moves, so the output is 4.

inputFormat

The first line contains an integer \(n\) representing the number of rows in the grid.

Then follow \(n\) lines, each consisting of a string \(s_i\) representing the \(i\)-th row of the grid. All rows have equal length which represents the number of columns \(m\).

outputFormat

Output a single integer which is the minimum number of moves needed to travel from the top-left corner to the bottom-right corner following the rule that you can only move to a cell with the same color. If no such path exists, output \(-1\).

## sample

3
a.a
aaa
a.a

4