🏡 index : github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: N2
category: NA
old_version: true
problem_code: N2
tags:
    - NA
layout: problem
---
###  All submissions for this problem are available. 

You are playing the game Heroes of Magical Might. Your hero is in a grid map divided into MxN squares.

There are three kinds of possible objects in each square:

- Obstacles: these can be trees, mountains, houses, and so on. Your hero cannot walk into these squares. These squares are represented by the characters '#'.
- Treasures: your hero can find some gold or earn experience points when collecting these treasures. These squares are represented by the characters '\*'.
- Gates: these gates form a complex interconnected network in the map. Your hero can travel almost instantly between the gates, represented by the characters '@'.

You control the hero turn by turn. In each turn, you can:

Choose one of the four possible directions, and move to the adjacent square in that direction. However, due to fog, your hero will only succeed with probability P. He may go in the remaining 3 directions with equal probability (1-P)/3. If the adjacent square is an obstacle or is outside the maze, the hero remains in the current square.

In addition, if your hero's current square is a gate, your hero could choose to enter the gate. He will appear in one of the remaining gates with equal probabilities, i.e. with probability 1/(Number of Gates - 1).

<pre>
.@.
@#@
</pre>For example, in the above map, suppose your hero's starting position is at (1,1) and P = 0.8. If the hero moves down in the first turn, he may succeed and end up in the gate at (2,1) with probability 0.8. With probability 0.2 / 3, he may go right and end up in the gate at (1,2). With probability 2\*0.2 / 3, he just remains at (1,1) since the top and left direction would lead him out of the maze.

If the hero choose to enter the gate at (2,2), he may end up at (1,2) or (2,3) with equal probability 1/2.

Find the optimum strategy to control your hero such that _the expected number of turns to collect the first treasure_ is minimized.

### Input

The first line contains t, the number of test cases (about 15). Then t test cases follow, preceded by empty lines. Each test case has the following form.

The first line contains two numbers M and N (1<=M,N<=20), describing the dimensions of the map.

Each line in the next M lines contains N characters describing the maze. The meanings of the characters are:

- '\*': treasure
- '#': obstacle
- '.': empty square
- '@': gate
- 'S': starting point of the hero

You are guaranteed that the hero can always collect at least one treasure with probability greater than 0. The number of gates will never be 1. There is exactly one 'S' character in the maze.

### Output

For each test case, output the minimum expected number of turns until the hero collects the first treasure, rounded to two decimal places.

### Example

<pre>
<b>Input:</b>
4

1 2
S*
0.7

1 2
S*
0

2 4
S##*
@##@
0.8

2 18
S...*.#@*......*@.
.@....#...........
0.6

<b>Output:</b>
1.43
3.00
3.50
6.41
</pre>