Preparing NOJ

穿越机房

1000ms 65536K

Description:

众所周知,在机房里想从一个地方到另一个地方很困难。因为机房里不仅有很多的 桌子,还摆了很多的椅子。现在,建冬哥想找嘉娃一起 apom,他不能在众目睽睽之下 对着嘉娃大吼,所以,他必须走到嘉娃跟前。

我们把机房分为宽度为 w,高度为 h w × h 个格子。每个格子或者是一张桌子, 或者有一把椅子,或者什么都没有。建冬哥不能通过有桌子的格子,可以以一个单位时 间通过什么都没有的格子,但是通过有椅子的格子时,建冬哥需要花两个单位时间。

现在给出建冬哥和嘉娃的位置,以及机房的构造,你能知道建冬哥最快要多长时间 才能到嘉娃身边吗? 

Input:

第一行 6 个整数 w,h,sr,sc,er,ec(3 w,h 20)w h 表示机房的大小, (sr,sc)表示建冬哥处在第 sr 行第 sc 列,同理 (er, ec) 表示目前嘉娃的位置。开始时建冬哥和 嘉娃肯定在机房里。接下来是一个 w × h 的矩阵,代表机房的地形:

 '.': 表示该格子没有障碍物,通过需要 1 个单位时间。

'*': 表示该格子有一把椅子,通过需要 2 个单位时间。

'x': 表示该格子是一张桌子,不能通过。 

Output:

一个整数,表示建冬哥到嘉娃所在位置的最短时间。之后加一个换行。 

Sample Input:

3 3 1 1 1 3 
.x*
*x.
*.*

Sample Output:

11

Note:

最后的输出结果为建冬哥经过路径上所有点的时间之和。 


本题由旧版NOJ导入,来源:第8届南京大学 ACM 程序设计大赛

Info

NOJ

Provider NOJ

Code NOJ1448

Tags

Submitted 9

Passed 1

AC Rate 11.11%

Date 04/20/2019 10:03:10

Related

Nothing Yet