b059. 4. 靈犬尋寶
標籤 :
通過比率 : 335人/378人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2007-12-08 07:44

內容

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


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

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

輸入說明

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

輸出說明
依行走之規則,若靈犬可以從其位置走到寶物的位置時,請列印出其使用之最少步數;若靈犬無法到達寶物的位置,請列印出單字『impossible』。
範例輸入 #1
4
3 6
4 5
5 4
6 3
3 3
7 5
2
1 1
0 2
0 1
4 3
範例輸出 #1
2
impossible
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
提示 :
標籤:
出處:
95學年度全國資訊學科能力競賽

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
39374 janetchung96 ... (Janet Chung) b059
cpp解法
65 2024-02-10 22:10
37649 harlivy_fore ... (噴火水雞肉飯) b059
可能的WA和RE原因
115 2023-09-24 11:57
24994 bubble60324@ ... (賢仔) b059
新手的解題想法
665 2021-04-10 20:24