Lazycat

Time limit2sMemory limit512 MB

Summary

Find the shortest walk on a grid with walls that starts at S, visits every food cell, then ends at the bed.

Level: Medium6 of 10
Topics: Dynamic programming, BFS, Bit manipulation
Solved: No attempts yet

Problem

The map of a house is given as an $n \times n$ grid. The picture below shows a $4 \times 4$ map.


B		F
X	X	F
F	X	X	F
S

Walls are marked 'X', food items are marked 'F', and the single bed is marked 'B'. The cat starts on the cell marked 'S', and that cell can be anywhere in the grid. The cat moves one cell at a time up, down, left, or right, and it cannot enter a cell marked 'X'. Find the smallest number of steps the cat needs to eat every food item and then reach the bed.

Input

The first line contains the grid size $n$ . ( $2 \le n \le 30$ )

Each of the next $n$ lines contains $n$ characters describing one row of the grid. The bed is 'B', a food item is 'F', a wall is 'X', an empty cell is the digit 0, and the cat's starting cell is 'S'. All letters are uppercase. 'B' and 'S' each appear exactly once, and 'F' appears at least once and at most ten times.

Output

Print one line with the smallest number of steps needed to eat every food item and then reach the bed. If the cat cannot eat every food item and reach the bed, print -1 instead.

Examples3

Example 1
Input
```
4
B0F0
XXF0
FXXF
S000
```
Expected output
```
11
```
Example 2
Input
```
2
SF
XB
```
Expected output
```
2
```
Example 3
Input
```
3
SXF
0X0
BX0
```
Expected output
```
-1
```