提示: 欢迎访问OurACM平台。
Problem 2250 不可能弹幕结界

Accept: 38    Submit: 118
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

咲夜需要穿过一片弹幕区,由于咲夜发动了符卡“The World”,所以弹幕是静止的。这片弹幕区以一个n*m的矩阵的形式给出。

‘.’表示这个位置是安全的,’x’表示这个位置上是有子弹的,禁止通行。咲夜每次能向左、右、下三个方向的相邻格子走,但是不能向上走。 同时由于时间有限,咲夜在进入每一行之后最多只能横向走k步。你可以简单地认为我们的目标就是从第0行走到第n+1行,起点和终点可以是在第0行和第n+1行的任意位置,当然第0行和第n+1行都是没有弹幕的。

然而这是号称不可能的弹幕结界,所以咲夜很可能无法穿过这片弹幕,所以咲夜准备了一个只能使用一次的技能,纵向穿越,她可以从任意位置直接穿越到另外任意一行的同一个位置(所在列不变),当然她只能向下穿越,不能向上穿越。穿越的距离越远,耗费的资源自然越多,所以她想知道最短的穿越距离,才能使她成功通过这片弹幕区。

Input

输入包含多组数据。

对于每组数据:

第一行输入三个整数n,m,k,如上所述。

接下下输入一个n×m的矩阵,’.’表示当前这格没有子弹,是安全的,’x’表示这各有子弹,禁止通行。

N<=1000,k<=m<=1000

Output

对于每组数据输出一个整数,表示最短的穿越距离。

Sample Input

6 5 2 x.x.. ..xx. .xxx. xx.xx xx..x ..x.x 4 4 1 .xxx .xxx ...x xx.x

Sample Output

3 2

Hint

对于第一组样例,最优解是从第一行第二列走到第三行第一列,然后跳到第6行第一列,穿越距离为(6 – 3) = 3。

long long类型请用%I64d输出

Source

FOJ有奖月赛-2017年4月(校赛热身赛)

Submit  Back  Status  Discuss