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
hide comments
vengatesh15:
20170906 10:55:51
Easy one AC in one go :) 

absur_siam:
20161130 04:47:12
States should be carefully recognized.A brute force bfs/dfs can lead to TLE. 

buttman:
20160713 18:51:05
Really good problem for bfs dfs 

Mauro Persano:
20141208 18:28:00
Simple problem but time limit is too strict for Scheme. Sigh. Last edit: 20141208 20:45:21 

Pablo Ariel Heiber:
20100927 23:26:55
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/ 
Added by:  Pablo Ariel Heiber 
Date:  20100927 
Time limit:  0.297s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC VB.NET 
Resource:  FCEyN UBA ICPC Selection 2010 