Minimum Portal Teleports

You are given an \(n \times n\) grid. The grid is described in a 2D map where each cell is one of the following:

• a wall, represented by #
• a void, represented by *
• a ground, represented by .

We use \((x, y)\) to denote the cell in the \(x\)th row and \(y\)th column. The player can only stand on ground cells. All cells outside the grid are considered walls.

You have a portal gun that can shoot two kinds of portals: blue and orange. The gun can only be fired in one of the four cardinal directions (up, down, left, right). When you choose a direction and a color, the gun will fire a portal which will be placed on the wall face of the first wall encountered in that direction, replacing any previous portal of the same color. Note that two portals of different colors cannot be placed on the same wall.

The player may move to an adjacent cell (up, down, left or right) if that cell is an open ground cell. Moreover, if the player attempts to move toward a wall cell that has a portal and both portals are currently built, then instead of stepping into the wall the player will immediately teleport. More formally, if the adjacent cell in the moving direction is a wall with, say, the blue portal, then the player will exit from the cell adjacent to the wall that holds the orange portal. The exit cell can be chosen from any of the four directions around that wall, as long as the cell is ground. (The same applies vice‐versa.)

The game starts with the player at cell \((1,1)\) and the goal is to reach cell \((n,n)\). Note that the cost is counted as the number of times the player passes through a portal (i.e. teleports). Moving or shooting the portal gun does not incur any cost. Determine the minimum number of portal teleports required to reach the destination. If it is impossible to reach the goal, output -1.

Portal Gun Shooting Details:

• From any ground cell, you may shoot the portal gun in one of the four directions. The shot travels cell‐by‐cell until it hits a wall. (Remember: cells outside the grid are walls.)
• The portal is placed on that wall (its location might be inside or outside the grid). If a portal of the same color already exists, it is replaced. However, you cannot shoot a portal onto a wall that already holds the other color’s portal.

Teleportation Details:

• If the player is adjacent to a wall cell that contains a portal and both portals exist, then moving in that direction will trigger a teleport.
• The player will appear on any adjacent ground cell to the wall holding the other portal. (There is always a choice if such a move is beneficial.)

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 50\)) representing the size of the grid. The following \(n\) lines each contain a string of length \(n\) consisting only of the characters #, *, and ., representing the grid.

It is guaranteed that cell \((1,1)\) and cell \((n,n)\) are ground (i.e. .).

outputFormat

Output a single integer: the minimum number of portal teleports needed to reach \((n,n)\) from \((1,1)\). If it is impossible, output -1.

sample

3
...
.#.
...

0