回分類題庫
d092: 2009 程式達人 F - 香腸寶藏問題
出處:

Difficulity : 1
Accepted : 13 Times | Submit :106 Times | Clicks : 1382
Accepted : 11 Users | Submit : 11 Users | Accepted rate : 100%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-06-02 00:41

Content :

WG是一個嗜香腸如命的人,為了要保護他心愛的香腸,他徒手建造了數個迷宮,並希望可以將香腸藏在各個迷宮中最深最安全的地方。


在WG的心中,他認為符合一個迷宮最安全的地方的條件是「這個地方到最近出口的最短距離要是要最大的」,也就是整個迷宮中的最深處。請各位寫一個程式幫WG計算他建造的迷宮中,最安全的地方離出口的最短距離是多少?

Input :

輸入多組測試資料,每組測資的第一行為迷宮的數量n。在每一個迷宮地圖的開頭會有一組數字p, q代表一個q*p大小的迷宮。接下來會有q行輸入,每行會有p個字,用來代表這個迷宮。迷宮只會由空白和0組成,空白代表可行走的地方,而0則代表障礙物不可行走的地方。出口只會在迷宮地圖的邊緣,且p和q是不大於100的正整數。

Output :

對每組測資輸出一行,代表這個迷宮中,最安全的地方到其最近出口的距離。

Sample Input :

2
10 7
0000000000
        00
000 000 00
000 000000
000 000000
00       0
000 000000
5 5
00000
0   0
0 0 0
0 0 
0 000

Sample Output :

9
5

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
21489. taop (4 ms , 442KB)
55342. johnny (12 ms , 342KB)
30254. henryokc (20 ms , 474KB)
42647. cp99303052 (24 ms , 504KB)
37120. nothinglo (252 ms , 562KB)
55118. ag100 (4 ms , 304KB)
55117. ag100 (8 ms , 308KB)
55343. johnny (10 ms , 348KB)
36913. king_of_laba (776 ms , 878KB)
36442. QQ (808 ms , 876KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡