TopCoder

User's AC Ratio

100.0% (28/28)

Submission's AC Ratio

65.5% (38/58)

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

3 3
2 2
1 3
1 2
1 1
3 3

Sample Output

4

Hints

Problem Source

原TIOJ1177 / TIOJ Contest #1020。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144