提交: 13 解决: 4

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

题目描述

Shining Knight is the embodiment of justice and he has a very sharp sword can even cleave

wall. Many bad guys are dead on his sword.

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.

wall. Many bad guys are dead on his sword.

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 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.

样例输入
Copy

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

样例输出 Copy

```
14
```