Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Navigation Game
Time Limit: 6000MSMemory Limit: 131072K
Total Submissions: 433Accepted: 110
Case Time Limit: 2000MS

Description

It's a game played on a specific board about navigation.

Here are the rules:
You can start voyage from any harbor chosen by yourself in the south (the bottom row), and the goal is to reach any harbor in the north (the top row) in shortest time.

Your boat may go north (upward), west (leftward) or east (rightward), just one grid each time, but it cannot navigate to rush to the grid of land or obstacles. In addition, it is considered useless (although sometimes not really) to go backward. So once you leave a grid, you cannot return to it.

It takes only one unit of time to go north, while the time spent on a horizontal (going west/east) movement depends on the number of continuous horizontal movements before this movement. It means that if X continuous horizontal movements have been done just before this movement, the amount of the units of time spent by the next horizontal movement is X + 1.

In the sea, there are some kinds of special objects.
- Obstacles. You cannot move into these grids.
- Fortune's wheels. In this game, Fortune's wheels really look like a weird wheel. You must meet Fortune's wheel ODD TIMES.
- Blessing stones. It costs NO time to go to this kind of grids.
- Invocations of storm. It costs DOUBLE time as normal to go to this kind of grids.

Input

There are two integers N and M in the first line. It is guaranteed that both N and M do not exceed 1000. N lines follows, and each line contains M characters describing the grid:

- In first and N-th of there N lines, 'H' stands for harbor, '.' stands for land.
- In other lines, '.', 'O','F','B' and 'S' stand for Empty grids, Obstacles, Fortune's wheels, Blessing stones and Invocations of storm respectively.

Output

If a solution exists, output an integer, which is the minimum time required; otherwise, output "No solution".

Sample Input

5 11
...H...H...
.O.BF.FS.O.
O.O.OOO.O.O
.O...F...O.
.....H.....

Sample Output

6

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator