TopCoder

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

31.6% (6/19)

Tags

Description

Last week - I saw a film
As I recall it was a horror film
Walked outside into the rain
Checked my phone and saw you rang and I
JIZZED IN MY PANTS

你正要回家,但你不想一直jizz,所以你最好不要接到電話
給你n*m的地圖,有些點是收訊不良的,所以安全,問你回到家的最短路徑有多長?
注意,如果你jizz了,那你必須換你的pants,但你只有k條備用的褲子可以換.
值得注意的一點:你會接到電話,只發生在你剛從一個收訊不良的位置走到有訊號的位置時。也就是說,這種情況下才需要換褲子。

Input Format

輸入的第一行有七個整數 n,m,k,sx,sy,tx,ty,其中n,m為地圖的高和寬,k是你多帶了幾條褲子,(sx,sy)表示第sx列第sy行是你的起點,(tx,ty)則是你家的位置。
接下來有n行,每行m個字元來表示地圖,如果該格為0,表示該格收訊不良是安全的,若為1則是不安全的。起點和終點則都是安全的。
所有輸入的n,m皆不超過100。

Output Format

輸出最少要走幾格才能回到你家,如果你的褲子鐵定不夠用,請輸出 "I WEAR A RUBBER AT ALL TIMES ITS A NECESSITY"

Sample Input 1

5 6 1 1 1 5 6
010100
100010
101110
101010
111010

Sample Output 1

13

Hints

Problem Source

原TIOJ1498 / problem setter: seanwu

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10