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勢力會統領多少土地呢?
第一行為一個整數n,代表地圖邊長。
再來為n行,每行是一個不含空白的字串,由l、r、u、d構成,依序代表左、右、上、下的箭頭。
1<=n<=2000
一個整數,代表先者(hellogameboy)可以佔領多少格。
原TIOJ1317 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin
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 |