e699: 11624 - Fire!
Tags : BFS
Accepted rate : 5人/6人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-11-18 06:49

Content

Joe在迷宮里工作。 不幸的是,迷宮的某些部分著火了,迷宮的設計者卻忽略了製定逃生計劃,幫助Joe逃脫迷宮。
考慮到Joe在迷宮中的位置以及迷宮的哪些方塊著火,您必須確定Joe是否可以在被火燒到之前離開迷宮,以及他需要花多久離開迷宮。
Joe和火每分鐘垂直或水平移動一個方格(非對角移動)。火勢從著火的每個方格蔓延到四個方向。
Joe可以從與迷宮邊緣接壤的任何方格離開迷宮。Joe和火都不能穿透牆壁的方格。

Input

輸入的第一行包含一個整數T,代表測資數量。
每組測資第一行包含兩個整數R和C (1 ≤ R,C ≤ 1000)。
接下來R行,每行C個字元,代表迷宮。
迷宮每個字元如下:
'#':代表一堵牆
'.':代表可以行走的方格
'J':Joe在迷宮中的初始位置
'F':著火的方格
每組測資中一定有一個'J'。

Output

對於每組測資,如果Joe在火到來之前無法離開迷宮,
輸出"IMPOSSIBLE"
否則,輸出Joe可以安全離開迷宮的最早時間(以分鐘為單位)。

Sample Input
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
Sample Output
3
IMPOSSIBLE
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
BFS
出處:
UVA [管理者:
ig99lp33lp33 (원스)
]


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