TopCoder

User's AC Ratio

95.0% (19/20)

Submission's AC Ratio

60.0% (24/40)

Description

你有看過X戰警嗎?裡面有個很厲害的萬磁王,他的特異功能是可以任意操縱磁性金屬。
但他在最後第三集被打了一針去除特異功能的基因,變成了一般人
經過九九八十一秒的修練才終於變回變種人,可惜特異功能已不如當時,現在的他只能勉強稱為磁鐵人
因為他不再能自由操縱金屬,只能把吸鐵全部往他的方向吸。

為了練習他變得頗虛弱的特異功能,他常常進行一個有趣的遊戲:
在一個n*n格的房間裡面有k個鐵塊,他可以站在這個房間外,對鐵塊們進行吸引, 他希望把這些鐵塊全部集中到同一個格子中
不過他只能站在四面牆之後,而不能站在角落或屋頂上,
所以每次使用特異功能, 可以使所有鐵塊往上下左右其中一個方向一起移動一格。
而這房間中有一些障礙物,如果在萬磁王吸引的時候,某個鐵塊受到障礙物阻擋,它就會停在原地不動
你可以假設不同鐵塊不會互相阻擋,也就是說一個格子中可以有多個鐵塊 (廢話,不然這問題問什麼)
除此以外, 房間四周牆壁視同障礙物。

試問萬磁王能否達成他的任務呢?

Input Format

每組測試資料只有一組輸入
第一行有一個整數n,代表房間長度
接下來有n行,每行n個字元
'.'代表空格,'#'代表障礙物,'x'代表鐵塊

1 <= 房間長度n <=500
1 <= 鐵塊數量k <=50

Output Format

對於每組輸入,請判斷萬磁王能否達成他的任務? (步數不限)
如果可以,請輸出"Strong!"
否則請輸出"Weak!"
(皆不用輸出雙引號)

Sample Input

5
x#..#
.#...
...#.
####.
x....

Sample Output

Strong!

Hints

萬磁王可以用以下的作法來達到目的:
(U代表往上吸, D代表往下吸, L代表往左吸, R代表往右吸)

DDRRURRUUU

兩個鐵塊會被集中在(1,4那格)
(行列以0開始計的話)

Problem Source

原TIOJ1238 / TIOJ例行賽IV, Problem Setter: kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 8
For Testdata: 1 ~ 1, Score: 8
For Testdata: 2 ~ 2, Score: 8
For Testdata: 3 ~ 3, Score: 8
For Testdata: 4 ~ 4, Score: 8
For Testdata: 5 ~ 5, Score: 8
For Testdata: 6 ~ 6, Score: 8
For Testdata: 7 ~ 7, Score: 8
For Testdata: 8 ~ 8, Score: 8
For Testdata: 9 ~ 9, Score: 8
For Testdata: 10 ~ 10, Score: 8
For Testdata: 11 ~ 11, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536
7 2000 65536 65536
8 2000 65536 65536
9 2000 65536 65536
10 2000 65536 65536
11 2000 65536 65536