409764: GYM103736 E Easy Problem

Now you have an $$$n \times n$$$ map. It contains obstacles '$$$*$$$', space '$$$.$$$', playerA '$$$a$$$', playerB '$$$b$$$'.

You can control two players to move up, down, left or right at the same time. For example, now $$$A$$$ and $$$B$$$ are in $$$(x_a,y_a)$$$ and $$$(x_b, y_b)$$$, next time the two players can go to:

• $$$(x_a, y_a+1)$$$ and $$$(x_b, y_b+1)$$$
• $$$(x_a, y_a-1)$$$ and $$$(x_b, y_b-1)$$$
• $$$(x_a+1, y_a)$$$ and $$$(x_b+1, y_b)$$$
• $$$(x_a-1, y_a)$$$ and $$$(x_b-1, y_b)$$$

Note that if the next location is a boundary or obstacle the player will not move.

You need to find the minimum number of steps when two players can meet.

The first line contains one integer $$$n$$$ $$$(2\leq n \leq 50)$$$.

For the next $$$n$$$ lines, each line contains a string of length $$$n$$$.

If in any case, the two players do not meet, print "no solution" in one line.

Otherwise, output the minimum number of steps.

6
.a....
*.....
......
..b*..
..**..
......

4

4
a*..
*...
....
...b

no solution

4
.ab.
....
....
....

2

7
..a.b..
.......
.......
.......
.......
.......
.......

4