題目描述

小華是一個愛狗的人，他有一隻名叫旺旺的小狗。有一天，他帶旺旺去公園散步，不小心讓牠跑走了。他很擔心，於是在公園附近貼了很多尋狗啟事，並留下了自己的電話號碼。幸運的是，他收到了一個神秘的簡訊，說知道旺旺在哪裡，但是要小華先回答一個問題。問題是這樣的： 給定一個由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)來求解這個問題。

輸入格式

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

輸出格式

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

Samples

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

原始資料

• Zero1 題號：b052
• Hydro 題號：Z1052
• Locale：zh_TW
• Display：open