forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFoxAndGo2.txt
181 lines (128 loc) · 4.2 KB
/
FoxAndGo2.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
PROBLEM STATEMENT
Fox Ciel is teaching her friend Jiro to play Go.
Ciel has just placed some white tokens onto a board.
She now wants Jiro to find the best possible sequence of moves.
(This is defined more precisely below.)
You are given a vector <string> board.
Character j of element i of board represents the cell (i,j) of the board:
'o' is a cell with a white token and '.' is an empty cell.
At least one cell on the board will be empty. Note that there are currently no black tokens on the board.
Each Jiro's move consists of adding a single black token to the board.
The token must be placed onto an empty cell.
Once Jiro places the token, some white tokens will be removed from the board according to the rules described in the next paragraphs.
The tokens on the board can be divided into connected components using the following rules:
If two tokens of the same color lie in cells that share an edge, they belong to the same component.
Being in the same component is transitive: if X lies in the same component as Y and Y lies in the same component as Z, then X lies in the same component as Z.
Note that each component of tokens is either completely white or completely black. Each component of tokens is processed separately.
For each component we check whether it is adjacent to an empty cell.
(That is, whether there are two cells that share an edge such that one of them is empty and the other contains a token from the component we are processing.)
If there is such an empty cell, the component is safe and its tokens remain on the board.
If there is no such empty cell, the component is killed and all its tokens are removed from the board.
There are also the following additional rules:
All white components must be processed before black ones (in any order).
If at least one white token was removed, then black components must not be processed at all.
Otherwise, all black components must be processed (in any order).
If at least one black token was removed, this is called a "suicide move". Such moves are invalid and Jiro is not allowed to make them.
Jiro's score is the total number of white tokens removed from the board after each of his moves is evaluated.
Return the maximal score he can get for the given board.
DEFINITION
Class:FoxAndGo2
Method:maxKill
Parameters:vector <string>
Returns:int
Method signature:int maxKill(vector <string> board)
CONSTRAINTS
-n will be between 2 and 19, inclusive.
-board will contain exactly n elements.
-Each element in board will contain exactly n characters.
-Each character in board will be 'o' or '.'.
-There will be at least 1 '.' in board.
EXAMPLES
0)
{"...",
".o.",
"..."}
Returns: 1
.A.
BoC
.D.
Jiro can put black pieces at A,B,C,D (in any order).
1)
{"o.",
"oo"}
Returns: 3
Jiro needs to place the black token into the empty cell. After that, the white component becomes unsafe and will be killed. The black component won't be processed, so the black token will remain on board.
2)
{".o.o.",
"o.o.o",
".o.o.",
"o.o.o",
".o.o."}
Returns: 0
Regardless of which empty cell he chooses, he will never kill any white component with this single black token.
On the other hand, his black token would always be killed.
Therefore, Jiro has no valid move on this board.
3)
{".o.o.",
"o.o.o",
".o.o.",
"o.o.o",
"....."}
Returns: 10
4)
{".o.o.o.o.o.",
"o.ooo.ooo.o",
".o.......o.",
"oo.......oo",
".o...o...o.",
"o...o.o...o",
".o...o...o.",
"oo.......oo",
".o.......o.",
"o.ooo.ooo.o",
".o.o.o.o.o."}
Returns: 4
5)
{"...ooo.....",
"...o.o.....",
".ooo.ooo...",
".o.....o...",
".ooo.ooo...",
"...o.o.....",
"...ooo.....",
"....o......",
"....o...ooo",
"....ooooo.o",
"........ooo"}
Returns: 38
6)
{"ooooooooooo",
"o.........o",
"o...ooo...o",
"o...o.o...o",
"o...ooo...o",
"o....o....o",
"o....oooooo",
"o..........",
"o.......ooo",
"o.......o.o",
"ooooooooooo"}
Returns: 0
Sometimes, making no moves at all is an optimal strategy.
7)
{"oo.o.ooo.o..o..",
"...ooo.o..oo.oo",
"o..o.o.ooo.o..o",
"oo.......oo.ooo",
"..oo.o.o.o.ooo.",
"..oo..oo..o.ooo",
"oo.o.oo..o.oooo",
".oo.o..ooo.o.oo",
"o..o.o.o.o.oo..",
".oo.oo...o....o",
"o.o.oo....oo..o",
".o.o..o.oo..ooo",
"o.o.o..o..o....",
"ooo.oooooooo..o",
"o..oo.o..o.ooo."}
Returns: 60