759 . 西洋棋騎士
TopCoder
Tags
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
1 1 1 3
1
3 2
Sample Output 1
4
Sample Input 2
3
1 1 2 2
1
1 3
1 1 2 2
1
1 3
Sample Output 2
-1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~18 | 無額外限制 | 100 |