1246 . 老鼠走迷宮
TopCoder
Tags
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 1
0 4
2 2
5 1
0 0
8 9
0 0 0
Sample Output 1
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 |