【問題K12】坦克任務。 [回前頁]

你是一名駕駛坦克的優秀指揮官。你的任務是深入敵營，躲過或是摧毀敵方重重砲臺的火力，成功抵達並摧毀敵方的基地。由於戰時的油料和砲彈都是珍貴的資源，你奉命利用衛星搜集來的地形資料，找到最短的路徑，並使用最少的砲彈完成此任務。

當你在砲臺所面對的方向時，你會瞬間被擊斃，因此你無法走入砲臺所面對的區域。但你可以先繞到砲臺所背對，或側對的區域，砲轟敵方的砲臺。而砲彈是無法穿過任何障礙物的。你的坦克和砲臺所發射的砲戰，只能朝正北，正東，正西，正南發射。當敵方砲臺被你摧毀時，砲臺的殘骸會留在原地，你的坦克無法直接通過。

若你一共走了a步，發出了b發砲彈，則你的任務是使a+b為最小。

輸入檔說明

每一筆測試資料，開頭兩個數字n，m，(n, m ³ 2) 分為表示此地圖的東西向，南北向的大小。接下來有m行，表示你所在的地方的地圖，地圖由 '  '（空白） 和 '*'（星號）所組成，空白表示你可以行走的路，星號是無法通過的地形，此地圖的最外一圈必定由星號所圍成。

接下來的四個數字start_x，start_y，destination_x，destination_y分別表示你的出發位置，和敵方基地的位置，地圖中最西北角的座標為(0,0)。再來1個數字num_of_enemy　(0 <= num_of_enemy <=4) 表示地圖上敵方砲臺的數目.接下來有num_of_enemy組的(x,y,d)，表示該砲臺的位置和面對的方向(方向N,E,S,W表示面對北,東,南,西)，相對於地圖上(上,右,下,左)。

最後一筆測試資料的開頭包含兩個0, 此時程式應結束。

n                輸出檔說明

對每一筆測試資料，輸出一行，告訴你的長官你所預計花費的行動數
"MINIMAL STEPS: n." 其中n是行動數: a+b (走了a步+發出b發砲彈)

若你發現你已受困，則輸出"IMPOSSIBLE."

n                範例輸入

n                範例輸出

IMPOSSIBL