TopCoder

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

58.8% (30/51)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11
11 2000 65536 262144 12