1177 . Maze
TopCoder
Tags
Description
在一個M*M大小的棋盤上，給你N個障礙物的位置，以及起始、終點位置S、E。請問從S走到E，每步只能往相鄰的四個格子之一前進，至少要幾步？
Input Format
第一列有兩個正整數M,N。(1<=M<=1000, 0<=N<=M*M)
第二列開始共N列每列有兩個正整數X,Y(1<=X,Y<=M)代表障礙物所在的座標。
最後兩列分別有兩個座標代表起點和終點的位置。
Output Format
請輸出從起點到終點所要走的最少步數，若無法到達請輸出-1。
Sample Input 1
3 3
2 2
1 3
1 2
1 1
3 3
2 2
1 3
1 2
1 1
3 3
Sample Output 1
4
Hints
Problem Source
原TIOJ1177 / TIOJ Contest #1020。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |