TopCoder

Thumb fhvirus
FHVirus
$\Huge{破台後跑十圈操場 ZCK請 FIN }$

User's AC Ratio

92.5% (49/53)

Submission's AC Ratio

34.2% (81/237)

Description

你是一個任職於大型資訊科技公司的上班族,今年26歲。回想起高中時第一次參加資訊競賽,進而點亮了自己對資訊領域的興趣。如今擁有了一份穩定的工作,生活也還算優渥,可說是十年來努力不懈的成果。

不過這看似完美的人生也有不幸的時刻。前些時日,你向你單戀多年的女性上司告白,卻被狠狠地拒絕掉了。為了排遣這鬱悶的情緒,你在下班後約了你的同事出來喝酒,將積累的怨氣好好發洩一番。

而現在,你正走在回家的路上,然而醉意未消的你,看著平常再熟悉不過的街道,竟然出現了十分詭異的變化。許多類似鬼魅的生物憑空出現,對你露出猙獰的面孔。

你現在所位於的街區可以看成一個$N\times M$的二維平面,你的初始位置是最左上角$(1,1)$,而你的家位於最右下角$(N,M)$。每一步你可以選擇往上、下、左、右移動,但因為你喝醉了,難以控制步伐,因此只能選擇一步前進$p$或$q$單位長的距離才能停下。你可以在街區內自由移動,但任何往街區外的移動都是不允許的。然而,街區內的某些格子點(即座標為整數的位置)已經被鬼佔領了,你可以在一步之內穿過鬼,但是你不能停留在有鬼的位置上,否則鬼會被驚動然後把你…(以下畫面請自行想像)。只要你停留在你家的位置上,就可以安全回到家。

不過故事還沒結束。你看到了街區位於$(a,b)$的位置,蹲坐著一位似乎是同樣看見可怕的鬼魂,而被嚇得六神無主的女高中生。你心想著一定要把這個女高中生帶回家,讓她免於鬼魅的驚嚇。之後她說不定會心存感激,然後之後你不管想跟她搞或是想讓她煮味噌湯給你喝都可以如願以償(咦)。不過想要把她帶回家,就一定要在與女高中生相同的位置停下才行。順帶一提,女高中生也是可以在一步之內穿過的,至於怎麼穿過就不好說了。

由於鬼實在是很可怕,你想要盡快的安全回到家,但又不能丟下女高中生不管。因此你想要知道,從目前位置出發,依照題目所述的行動方式,經過女高中生,最後安全回到家,所需的最少步數是多少,或是回報無法達成。

Input Format

輸入的第一行有兩個正整數$N,M$,代表街區的長與寬。
接下來一行有兩個正整數$p,q$,代表每次可以選擇的步數長度。
接下來一行兩個正整數$a,b$,表示女高中生的位置座標。

接下來共$N$行,每行有$M$個整數,對於第$i$行第$j$個整數$c_{ij}$,
若$c_{ij}=0$,表示位置$(i,j)$是安全的,可以停留。
若$c_{ij}=1$,表示位置$(i,j)$被鬼佔領,不可停留。

保證起始位置、終點位置、女高中生的位置都是安全的。

對於所有測試資料,保證$N,M,p,q \leq 1000$,$1\leq a\leq N$,$1\leq b\leq M$,$c_{ij}\in \{ 0,1 \}$對於所有$1\leq i\leq N,1\leq j\leq M$。

Output Format

輸出一個整數,表示與女高中生一同回家所需的最少步數。若無法達成,請輸出$-1$。

Sample Input

6 5
2 3
3 4
0 0 1 0 0
0 0 1 0 0
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0
0 0 0 1 0

Sample Output

5

Hints

一個合法的最短路徑為$(1,1)$->$(1,4)$->$(3,4)$->$(3,2)$->$(6,2)$->$(6,5)$,其長度為$5$。

Problem Source

110學年度建國中學校內資訊能力競賽初試pC

Subtasks

No. Testdata Range Constraints Score
1 0~16 $N, M,p,q \le 6$ 16
2 17~25, 58~63 $c_{i, j} = 0$ 對於所有的 $1 \le i \le N, 1 \le j \le M$ 17
3 26~36, 58~63 $p = q = 1$ 18
4 0~63 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 4
1 1000 131072 65536 1 4
2 1000 131072 65536 1 4
3 1000 131072 65536 1 4
4 1000 131072 65536 1 4
5 1000 131072 65536 1 4
6 1000 131072 65536 1 4
7 1000 131072 65536 1 4
8 1000 131072 65536 1 4
9 1000 131072 65536 1 4
10 1000 131072 65536 1 4
11 1000 131072 65536 1 4
12 1000 131072 65536 1 4
13 1000 131072 65536 1 4
14 1000 131072 65536 1 4
15 1000 131072 65536 1 4
16 1000 131072 65536 1 4
17 1000 131072 65536 2 4
18 1000 131072 65536 2 4
19 1000 131072 65536 2 4
20 1000 131072 65536 2 4
21 1000 131072 65536 2 4
22 1000 131072 65536 2 4
23 1000 131072 65536 2 4
24 1000 131072 65536 2 4
25 1000 131072 65536 2 4
26 1000 131072 65536 3 4
27 1000 131072 65536 3 4
28 1000 131072 65536 3 4
29 1000 131072 65536 3 4
30 1000 131072 65536 3 4
31 1000 131072 65536 3 4
32 1000 131072 65536 3 4
33 1000 131072 65536 3 4
34 1000 131072 65536 3 4
35 1000 131072 65536 3 4
36 1000 131072 65536 3 4
37 1000 131072 65536 4
38 1000 131072 65536 4
39 1000 131072 65536 4
40 1000 131072 65536 4
41 1000 131072 65536 4
42 1000 131072 65536 4
43 1000 131072 65536 4
44 1000 131072 65536 4
45 1000 131072 65536 4
46 1000 131072 65536 4
47 1000 131072 65536 4
48 1000 131072 65536 4
49 1000 131072 65536 4
50 1000 131072 65536 4
51 1000 131072 65536 4
52 1000 131072 65536 4
53 1000 131072 65536 4
54 1000 131072 65536 4
55 1000 131072 65536 4
56 1000 131072 65536 4
57 1000 131072 65536 4
58 1000 131072 65536 2 3 4
59 1000 131072 65536 2 3 4
60 1000 131072 65536 2 3 4
61 1000 131072 65536 2 3 4
62 1000 131072 65536 2 3 4
63 1000 131072 65536 2 3 4