Server Time：

77 . 快晴

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio in this contest

20.0% (2/10)

Submission's AC Ratio in this contest

4.5% (2/44)

Tags

2020 高階競技程式設計 - Contest #7

Description

明明是梅雨季節，可是神社這裡卻完全沒有下雨；
雖說連續的大晴天十分詭異，但這是飛行的好天氣，靈夢決定做個水平飛行訓練

水平飛行訓練採用可遇到許多障礙物的低空飛行，
而靈夢的飛行速度至多是每秒 $K$ 單位距離，有四個基本飛行方向：上、下、左、右
她將飛行的地圖利用符號表示，且地圖的左上角為座標 $(1, 1)$，右下角則為 $(N, M)$
靈夢想計算從起點 $(a_0, b_0)$ 飛到終點 $(a_1, b_1)$ 最少需要花多少時間

注意：靈夢在 $1$ 秒內只能直線飛行，不能在 $1$ 秒內中途轉彎。

Input Format

第一列 $N, M, K$ 表示飛行區域縱長與橫寬幾單位、以及靈夢的速度 $(1 \le N, M, K \le 1000)$
接著給定地圖，以 # 符號表示障礙物及 . 表示可飛行的區域
最後 4 個整數 $a_0, b_0, a_1, b_1$ 表示起點與終點 $(1\le a_0, a_1 \le N; 1 \le b_0, b_1 \le M)$

Output Format

輸出靈夢至少需要花幾秒從起點到達終點；
若不能從起點飛到終點則輸出 $-1$

Sample Input 1

5 8 2
........
.#.....#
#.#..###
.....#.#
........
2 7 4 2

Sample Output 1

4

Sample Input 2

10 10 1
##########
#.........
#.#######.
#.#.....#.
#.#.###.#.
#.#.#.#.#.
#.#.#.#.#.
#.#.#...#.
#.#.#####.
#.#.......
6 6 10 2

Sample Output 2

48

Hints

第一筆測資靈夢先向左移動 $2$ 單位，接著往下 $2$ 單位，最後花 $2$ 秒向左移動 $3$ 單位

Problem Source

Subtasks

No. Testdata Range Score
1 0~56 100

Testdata and Limits

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