Problem C. Harder Sokoban Problem ≡

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

The game of sokoban is played in a rectangular labirinth of N by N cells with each cell either empty, denoted by '.' character (ASCII 46), or occupied by wall, denoted by '#' character (ASCII 35). There is also a single destination cell, denoted by '*' character (ASCII 42).

One player and one container are located in the empty cells of the labirinth. The player can move between the empty cells in horizontal or vertical direction. If the cell where the player tries to move is occupied by container, the container is "pushed" to the next cell in the same direction. That next cell must, of course, be empty.

The objective of the game is well-known: to place the container in the destination cell with the minimum number of moves. Your task, however, is different: given the field, select starting position for the player and the container so as to maximize the required number of moves.

Input file format

First line of input contains number N — the field size. The following N lines consist of N characters each — representation the field. The input field always contains at least one empty cell adjacent to the destination cell.

Output file format

Output file must contain a single integer — the maximal number of moves.

Constraints

2 ≤ N ≤ 25

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
2
..
.*
 
0
2 
3
..#
...
..*
 
10
0.039s 0.009s 15