b052: 找出失蹤的狗(20230602BOSS由黃皓紀首名挑戰成功)
Tags :
Accepted rate : 16人/18人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-06-02 14:57

Content

小華是一個愛狗的人,他有一隻名叫旺旺的小狗。有一天,他帶旺旺去公園散步,不小心讓牠跑走了。他很擔心,於是在公園附近貼了很多尋狗啟事,並留下了自己的電話號碼。幸運的是,他收到了一個神秘的簡訊,說知道旺旺在哪裡,但是要小華先回答一個問題。問題是這樣的: 給定一個由0和1組成的二維陣列,表示公園的地圖。0表示空地,1表示障礙物。旺旺在地圖上的某個位置,用2表示。小華在地圖上的另一個位置,用3表示。小華每次可以向上、下、左、右移動一格,但不能移動到障礙物或地圖外。請問小華最少需要移動幾步才能找到旺旺?如果無法找到旺旺,則回答-1。 請幫助小華解決這個問題,找回他心愛的狗狗。 

 

輸入:第一行包含兩個正整數n和m,表示地圖的行數和列數。接下來n行,每行包含m個數字,表示地圖的內容。保證地圖中只有一個2和一個3。

輸出:一行包含一個整數,表示小華最少需要移動的步數。如果無法找到旺旺,則輸出-1。

範例輸入:

5 5

0 0 0 0 0

0 1 1 1 0

0 1 2 1 0

0 1 3 1 0

0 0 0 0 0

範例輸出:

1

提示:可以使用廣度優先搜尋(BFS)來求解這個問題。

 
Input

輸入:第一行包含兩個正整數n和m,表示地圖的行數和列數。接下來n行,每行包含m個數字,表示地圖的內容。保證地圖中只有一個2和一個3。

Output

輸出:一行包含一個整數,表示小華最少需要移動的步數。如果無法找到旺旺,則輸出-1。

Sample Input #1
5 5

0 0 0 0 0

0 1 1 1 0

0 1 2 1 0

0 1 3 1 0

0 0 0 0 0
Sample Output #1
1
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (50%): 1.0s , <1K
不公開 測資點#1 (50%): 1.0s , <1K
Hint :
Tags:
出處:
[管理者:
kichan@g.pui... (陳嘉賢CHAN KA IN)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」