Harder Sokoban Problem

Sokoban is played on a rectangular grid of $N \times N$ cells. Each cell is either empty, written as . (ASCII 46), or a wall, written as # (ASCII 35). There is also exactly one destination cell, written as * (ASCII 42).

One player and one container start on two of the empty cells. The player moves one step at a time to a horizontally or vertically adjacent empty cell. If the player steps toward the cell that holds the container, that container is pushed one cell further in the same direction; the cell it is pushed into must be empty (it cannot be pushed into a wall or off the grid).

The usual goal of Sokoban is to bring the container onto the destination cell using the fewest moves. One move is a single step of the player, and a step that pushes the container still counts as one move.

Your task is the opposite. Given the grid, you choose the starting cells of the player and the container so that the minimum number of moves needed to bring the container onto the destination is as large as possible. Output that maximum.

Placements from which the container can never reach the destination are not considered. Placing the container directly on the destination needs 0 moves, so the answer is always at least 0.

The first line contains the grid size $N$. Each of the next $N$ lines contains $N$ characters describing the grid. The grid always contains at least one empty cell adjacent to the destination cell.

Print a single integer: the largest possible value of the minimum number of moves needed to bring the container onto the destination.

• $2 \le N \le 25$