ESCJAILA - Escape from Jail Again

A new International Common Prison for Criminals (ICPC) was built, and your old friend Harry was moved there as a prisoner. As before, the new ICPC is one of the most secure prisons in the world. It was designed by and old gamer and as such, the prison is not necessarily closed, but only an incredibly logical and fast mind can get out.

The new ICPC can be represented as a grid of square cells. Each cell is empty, or it contains a wall, a door, an opening button or a closing button. Harry was accommodated in an empty cell, and all doors were closed. Nevertheless, Harry told you that he will try to escape. Each time Harry is in a cell, he can move in a single step to an adjacent cell (i.e., a cell that shares a side with his current location). Each time Harry steps on a cell that contains an opening button, all doors open, while each time he steps on a cell that contains a closing button, all doors close. Harry can walk around as he wants within the prison, although he cannot move to a cell that contains a wall, neither to a cell that contains a door if the doors are closed.

To escape from the prison, Harry needs to step outside, which means placing himself in one of the cells on the sides and then taking one extra step out in the direction opposite to the prison.

You obtained a map of the prison, and Harry deserves your advise. Tell him the minimum number of steps he needs to escape, or warn him that there is no way to get out.

Input

Each test case is described using several lines. The first line contains two integers N and M indicating respectively the number of rows and columns of the grid that represents the prison (1 ≤ N, M ≤ 100). Line i of the next N lines describes row i of the grid using a string of exactly M characters, where character j represents cell j of that row. This string only contains the following characters with the indicated meanings: “H” is the empty cell where Harry is at the beginning; “.” is an empty cell where Harry is not at the beginning; “W” is a wall; “D” is a door; “O” is an opening button; and “C” is closing button. You may assume that within each test case there is exactly one character “H”. The end of input is indicated with a line containing the number −1 twice.

Output

For each test case, output a single line with a single integer representing the minimum number of steps Harry needs to escape the prison, or the number −1 if it is impossible for him to do so.

Example

Input: 
5 8
WWWWWWW.
WHDC...D
W.WW.WCW
W.OW..OW
.WWWWWWW
3 3
ODO
DHD
ODO
3 7
WWWWWWW
DH..OCD
WWWWWWW
4 1
W
H
O
W
1 13
HOW.DO.COW.DO
-1 -1 Output:
21
-1
8
1
1

Added by:Pablo Ariel Heiber
Date:2010-09-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010

hide comments
2022-01-15 09:23:44
@ sarkybastard: ok bastard
2020-09-24 23:47:19
@s_tank00_: it's a prison - do you think the gates would be open or closed?
2020-08-29 10:50:57
initially the gates are closed or open?
2020-08-18 14:31:39
can someone please explain how answer for the first testcase is 21 :(
2017-09-06 10:55:51
Easy one AC in one go :-)
2016-11-30 04:47:12
States should be carefully recognized.A brute force bfs/dfs can lead to TLE.
2016-07-13 18:51:05
Really good problem for bfs dfs
2014-12-08 18:28:00 Mauro Persano
Simple problem but time limit is too strict for Scheme. Sigh.

Last edit: 2014-12-08 20:45:21
2010-09-27 23:26:55 Pablo Ariel Heiber
The "Again" part of the title remembers the escape from jail problem in FCEyN UBA ICPC Selection of 2008: https://www.spoj.pl/problems/ESJAIL/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.