TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

91.7% (11/12)

Description

大家都知道,『老鼠走迷宮』是個非常經典的題目!今天資訊社的老鼠又要挑戰一個嶄新的迷宮了!
這個迷宮跟大多數的迷宮一樣,有很多的障礙物(誤),每個障礙物都是圓形,擺在格子正中心且半徑為半單位長。老鼠則必須從指定的起點拉著球跑到指定的終點。
不過因為資訊社的老鼠太威,一次必須要剛好直線走五單位的距離(不限方向)並且花費一單位的『強者能』,甚至可以無視障礙物穿越,但是雖然老鼠很威但是球不威,所以球無法穿過障礙物(亦即五距離的路程中不能有障礙物),而且老鼠每次停下來時都一定要剛好在格子的中心點,而且雖說是拉球,球和老鼠其實總是在同一個位置。現在給你一張地圖,你有辦法幫助跟老鼠講說他至少要花費多少『強者能』嗎?如果無法走到,請趕快跟老鼠說皮皮測資出錯了!

Input Format

輸入可能包含多筆測試資料。
每筆測試資料的第一行有三個以空格分開的正整數M, N, K,代表迷宮大小為MxN以及有K個障礙物(2 ≦ M, N ≦ 1,200, 0 ≦ K ≦ 1,000,000)
接下來有K行,每行兩個以空格分開的正整數代表障礙物的座標X,Y(0 ≦ X < M, 0 ≦ Y < N)
第K+2行有兩個正整數X1, Y1,表示起點之座標(0 ≦ X1 < M, 0 ≦ Y1 < N)
第K+3行有兩個正整數X2, Y2,表示終點之座標(0 ≦ X2 < M, 0 ≦ Y2 < N)
起點、終點和障礙物的座標都不會重疊。
當M = N = K = 0時,代表輸入結束,聰明的你當然不會對它輸出任何資料。

Output Format

請輸出至少需要花費多少強者能。如果無論如何都無法走到終點的話,請輸出"No Way!"。

Sample Input

9 10 3
0 4
2 2
5 1
0 0
8 9
0 0 0

Sample Output

3

Hints

範例測資的地圖如下:

紅色線因有障礙物擋住而無法通過。

Problem Source

原TIOJ1246 / INFOR 21st幹部考(prob B)。Problem Setter:peter50216。

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 (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10