TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

28.6% (2/7)

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

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

Sample Output

13

Hints

Problem Source

原TIOJ1498 / problem setter: seanwu

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144