### 1298: Oh, my goddess

[提交] [状态] [讨论版] [命题人:]

#### 题目描述

Shining Knight is the embodiment of justice and he has a very sharp sword can even cleave
One day, two evil sorcerer cgangee and Jackchess decided to give him some color
to see. So them kidnapped Shining Knight's beloved girl--Miss Ice! Them built a M x N
maze with magic and shut her up in it.
Shining Knight arrives at the maze entrance immediately. He can reach any adjacent empty
square of four directions -- up, down, left, and right in 1 second. Or cleave one adjacent wall in 3
seconds, namely, trun it into empty square. It's the time to save his goddess! Notice: Shining
Knight won't leave the maze before he find Miss Ice.

#### 输入

The input consists of blocks of lines. There is a blank line between two blocks.
The first line of each block contains two positive integers M <= 100 and N <= 100
separated by one space. In each of the next M lines there is a string of length N contents
O and #.
O represents empty squares. # means a wall.
At last, the location of Miss Ice, ( x, y ). 1 <= x <= M, 1 <= y <= N.
(Shining Knight always starts at coordinate ( 1, 1 ). Both Shining and Ice's location
guarantee to not be a wall.)

#### 输出

The least amount of time Shining Knight takes to save his goddess in one line.

#### 样例输入

3 5
O####
#####
#O#O#
3 4


#### 样例输出

14


[提交] [状态]