Problem : 26 - 靈犬尋寶

Problem Statistics

Solved Member: 36　　Submission: 111　　User Tried: 41

Statement:

正方形(左下角座標為(0,0)，右上角座標為(99,99))的格網上，有一隻靈犬要尋找一個寶物，格網上除了靈犬與寶物之外，還有一些障礙物。一般情況下，只要不超出格網的邊界，靈犬的每一步最多有8個方向可供選擇，如圖一；但是必須注意，只有在A點沒有障礙物時才可以選擇方向1或方向2，只有在B點沒有障礙物時才可以選擇方向3或方向4，只有在C點沒有障礙物時才可以選擇方向5或方向6，只有在D點沒有障礙物時才可以選擇方向7或方向8。如果靈犬可以從出發的位置走到寶物的位置，其總共使用的步數，理論上應有一個最小值；但是靈犬也有可能無法走到寶物的位置。過程中，靈犬不可以走到障礙物的位置上。

以圖二為例，有多達4個障礙物介於靈犬與寶物之間，但是靈犬最快只要2步就可以到達寶物的位置。圖三是另一個例子，靈犬的位置靠近角落，雖然只有2個障礙物，靈犬卻無法到達寶物的位置。

請撰寫一個程式，若靈犬可以從最初位置走到寶物的位置時，請列印出其使用之最少步數；若靈犬無法到達寶物的位置，請列印出單字『impossible』。

Input:Output:

第一行為一個整數n，代表障礙物的個數，0 ≤ n ≤ 1000。接下來的n行，每行表示一個障礙物的座標，其橫座標值與縱座標值間以一個空白隔開。
再下來的一行，表示靈犬的最初位置，其橫座標值與縱座標值間以一個空白隔開。
最後一行，代表寶物的位置，其橫座標值與縱座標值間以一個空白隔開。
注意：輸入之障礙物、靈犬、寶物皆在不同位置。所有橫、縱座標值均為介於0(含)至99(含)之間的整數。

依行走之規則，若靈犬可以從其位置走到寶物的位置時，請列印出其使用之最少步數；若靈犬無法到達寶物的位置，請列印出單字『impossible』。

Sample Input:Sample Output:

1:
4
3 6
4 5
5 4
6 3
3 3
7 5

2:
2
1 1
0 2
0 1
4 3

1:
2

2:
impossible

Source:

95 全國賽

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	1000ms	65536kb	25
2	1000ms	65536kb	25
3	1000ms	65536kb	25
4	1000ms	65536kb	25