你有看過X戰警嗎?裡面有個很厲害的萬磁王,他的特異功能是可以任意操縱磁性金屬。
但他在最後第三集被打了一針去除特異功能的基因,變成了一般人
經過九九八十一秒的修練才終於變回變種人,可惜特異功能已不如當時,現在的他只能勉強稱為磁鐵人
因為他不再能自由操縱金屬,只能把吸鐵全部往他的方向吸。
為了練習他變得頗虛弱的特異功能,他常常進行一個有趣的遊戲:
在一個n*n格的房間裡面有k個鐵塊,他可以站在這個房間外,對鐵塊們進行吸引, 他希望把這些鐵塊全部集中到同一個格子中
不過他只能站在四面牆之後,而不能站在角落或屋頂上,
所以每次使用特異功能, 可以使所有鐵塊往上下左右其中一個方向一起移動一格。
而這房間中有一些障礙物,如果在萬磁王吸引的時候,某個鐵塊受到障礙物阻擋,它就會停在原地不動
你可以假設不同鐵塊不會互相阻擋,也就是說一個格子中可以有多個鐵塊 (廢話,不然這問題問什麼)
除此以外, 房間四周牆壁視同障礙物。
試問萬磁王能否達成他的任務呢?
每組測試資料只有一組輸入
第一行有一個整數n,代表房間長度
接下來有n行,每行n個字元
'.'代表空格,'#'代表障礙物,'x'代表鐵塊
1 <= 房間長度n <=500
1 <= 鐵塊數量k <=50
對於每組輸入,請判斷萬磁王能否達成他的任務? (步數不限)
如果可以,請輸出"Strong!"
否則請輸出"Weak!"
(皆不用輸出雙引號)
萬磁王可以用以下的作法來達到目的:
(U代表往上吸, D代表往下吸, L代表往左吸, R代表往右吸)
DDRRURRUUU
兩個鐵塊會被集中在(1,4那格)
(行列以0開始計的話)
原TIOJ1238 / TIOJ例行賽IV, Problem Setter: kelvin
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 8 |
2 | 1 | 8 |
3 | 2 | 8 |
4 | 3 | 8 |
5 | 4 | 8 |
6 | 5 | 8 |
7 | 6 | 8 |
8 | 7 | 8 |
9 | 8 | 8 |
10 | 9 | 8 |
11 | 10 | 8 |
12 | 11 | 12 |