TopCoder

$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

7.7% (4/52)

Tags

Description

hellogameboy正在進行一個神秘的計畫
他打算以H的力量來征服全世界,讓世界都屈服在他的H勢力之下
這時候正義的hallogameboy挺身而出,決心鼎力維持這個世界的正直

想像這世界是一個n*n的格子棋盤,每個格子都是一個城市
而時事潮流總有固定的流向,因此對於每個格子都有一個"潮流傳播方向" (上、下、左、右之一)
若某個城市的潮流是流向棋盤邊界外,當然,這個城市的潮流就不會傳播給任何人

hellogameboy和hallogameboy將輪流展開行動,
由hellogameboy先展開H的攻勢,再換hallogameboy進行正直防守.....
攻防不斷交替地進行,直到所有城市都被佔領

一開始所有城市都是純潔的,沒有受到任何佔領
而he(a)llohameboy將選擇一個"源流城市"佔領
H(正直)的力量就會從這個源流城市開始沿著每個格子的潮流傳播方向傳播
路上的城市都被佔領,直到某個潮流傳出邊界,或是遇到某個已被佔領的城市才停止。

以上圖為例(佔領攻防還沒結束,也不是最佳佔領策略)
hellogameboy先選擇(2,2),並佔領紅色的12格
再來換hallogameboy,選擇(5,7),佔領藍色的8格
再來又輪到hellogameboy,選擇(5,6),佔領綠色2格
hallogameboy再選擇(2,4),佔領黃色等5格……

給定一個地圖,假設hallogameboy和hellogameboy都是絕頂聰明的人物
那麼請問,最後hellogameboy將以H勢力會統領多少土地呢?

Input Format

第一行為一個整數n,代表地圖邊長。
再來為n行,每行是一個不含空白的字串,由l、r、u、d構成,依序代表左、右、上、下的箭頭。

1<=n<=2000

Output Format

一個整數,代表先者(hellogameboy)可以佔領多少格。

Sample Input 1

6
drludl
rudlru
dldldl
rldlrd
uuudlr
ddlluu

Sample Output 1

19

Hints

Problem Source

原TIOJ1317 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 20000 131072 262144 1
1 20000 131072 262144 2
2 20000 131072 262144 3
3 20000 131072 262144 4
4 20000 131072 262144 5
5 20000 131072 262144 6
6 20000 131072 262144 7
7 20000 131072 262144 8
8 20000 131072 262144 9
9 20000 131072 262144 10
10 20000 131072 262144 11
11 20000 131072 262144 12
12 20000 131072 262144 13
13 20000 131072 262144 14
14 20000 131072 262144 15
15 20000 131072 262144 16
16 20000 131072 262144 17