題目描述

下圖給出了一個迷宮的平面圖，其中標記為 X 的為障礙，標記為 O 的為可以通行的地方。

OXOOOO
OOOXOO
OOXOOX
XXOOOO

迷宮的入口為左上角，出口為右下角，在迷宮中，只能從一個位置走到這個它的上、下、左、右四個方向之一。(確保迷宮左上角和右下角都是O)

對於上面的迷宮，從入口開始，到出口的最短路徑一共10  步。對於下面這個更複雜的迷宮 ( 50行 50列)，請找出一種通過迷宮的方式的最少步數。若不能離開返回 -1。

輸入格式

第一行兩個正整數 n 和 m 分別代表行數和列數 (n,m <= 50)

跟著就是 n 行和 m 列的迷宮地圖

輸出格式

輸出一個整數, 代表離開迷宮的最少步數 或 -1 代表不能離開迷宮

Samples

4 6
OXOOOO
OOOXOO
OOXOOX
XXOOOO

10

原始資料

• Zero1 題號：b585
• Hydro 題號：Z1585
• Locale：zh_TW
• Display：open