TopCoder

abcabcabc

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (4/4)

Description

在一個 $N \times N$ 的西洋棋盤上，有一隻騎士在第 $a$ 行第 $b$ 列的格子上，這隻騎士想要移動到第 $c$ 行第 $d$ 列的格子，但是只能照著西洋棋騎士日字形的走法 ( https://zh.wikipedia.org/zh-tw/%E9%A6%AC_(%E5%9C%8B%E9%9A%9B%E8%B1%A1%E6%A3%8B) ) ，另外有幾個格子有陷阱，所以騎士不能停在這些格子上，請問到目的地所需的最少步數為多少？

Input Format

輸入第一行有一個正整數 $N$ 代表棋盤的大小，輸入的第二行有四個正整數 $a,b,c,d$ 代表騎士的初始位置和目的地位置，輸入第三行有一個整數 $T$ 代表陷阱格子的數目，接下來 $T$ 行中每一行都有兩個正整數 $x, y$ 代表第 $x$ 行第 $y$ 列的格子是陷阱。

$2 \le N \le 1000$
$1 \le a, b, c, d \le N$
$0 \le T \le N^ 2 - 2$
$1 \le x, y \le N$
保證不會有位置重複的陷阱且初始位置和目的地都不是陷阱。

Output Format

輸出一個整數代表需要的步數，若騎士永遠無法達到目的地，則輸出 -1 。

Sample Input 1

4
1 1 1 3
1
3 2

Sample Output 1

Sample Input 2

3
1 1 2 2
1
1 3

Sample Output 2

-1

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~18	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	2000	524288	65536	1 2
1	2000	524288	65536	1 2
2	2000	524288	65536	2
3	2000	524288	65536	2
4	2000	524288	65536	2
5	2000	524288	65536	2
6	2000	524288	65536	2
7	2000	524288	65536	2
8	2000	524288	65536	2
9	2000	524288	65536	2
10	2000	524288	65536	2
11	2000	524288	65536	2
12	2000	524288	65536	2
13	2000	524288	65536	2
14	2000	524288	65536	2
15	2000	524288	65536	2
16	2000	524288	65536	2
17	2000	524288	65536	2
18	2000	524288	65536	2

759 . 西洋棋騎士