/home/toolbox/public_html/solutions/8/852/vicingo.cpp
1 #include <cstdio>
2 #include <iostream>
3 #include <vector>
4 #include <cstring>
5
6 using namespace std;
7
8 #define DEBUG
9 #undef DEBUG //uncomment this line to pull out print statements
10 #ifdef DEBUG
11 #define TAB '\t'
12 #define debug(a, end) cout << #a << ": " << a << end
13 #else
14 #define debug(a, end)
15 #endif
16
17 typedef pair<int, int> point;
18 typedef long long int64; //for clarity
19 typedef vector<int> vi; //?
20 typedef vector<point> vp; //?
21 template<class T> void chmin(T &t, T f)
22 {
23 if (t > f) t = f; //change min
24 }
25 template<class T> void chmax(T &t, T f)
26 {
27 if (t < f) t = f; //change max
28 }
29
30 #define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())
31 #define SORT(c) sort((c).begin(),(c).end())
32 #define FOR(i,a,b) for (int i=(a); i < (b); i++)
33 #define REP(i,n) FOR(i,0,n)
34 #define CL(a,b) memset(a,b,sizeof(a))
35 #define CL2D(a, s, len, wid) memset(a, s, sizeof(a[0][0])*len*wid)
36
37 /*global variables*/
38 const int LENGTH = 11, WIDTH = 11;
39 char board[LENGTH][WIDTH];
40
41 char white_num = '2';
42 char black_num = '3';
43 char bad_spot = '9';
44
45 char black = 'X';
46 char white = 'O';
47 char empty = '.';
48
49 int rangex[4] = {1, 0, -1, 0};
50 int rangey[4] = {0, 1, 0, -1};
51 /*global variables*/
52
53 void floodfill_bad(int, int);
54
55 char opposite(char c)
56 {
57 if (c == black)
58 return white;
59 else return black;
60 }
61
62 void dump()
63 {
64 //dump data
65 for (int i = 0; i < LENGTH; ++i)
66 {
67 for (int j = 0; j < WIDTH; ++j)
68 printf("%c", board[i][j]);
69 printf("\n");
70 }
71 }
72
73 void getInput()
74 {
75 for (int i = 1; i < LENGTH-1; ++i)
76 for (int j = 1; j < WIDTH-1; ++j)
77 scanf("%c%*[\n]", &board[i][j]);
78 }
79
80 bool floodfill(int x, int y, char check)
81 {
82 debug("floodfill", TAB);
83 debug(x, TAB);
84 debug(y, TAB);
85 debug(check, endl);
86 /*
87 true = hit opposite color
88 false = !true
89 */
90 //dump();
91 for (int i = 0; i < 4; ++i)
92 {
93 if (board[x+rangex[i]][y+rangey[i]] == empty)
94 {
95 char c;
96 (check == white) ? c = white_num : c = black_num;
97 board[x+rangex[i]][y+rangey[i]] = c;
98 //floodfill again
99 if (floodfill(x+rangex[i], y+rangey[i], check))
100 {
101 board[x+rangex[i]][y+rangey[i]] = bad_spot;
102 //floodfill_bad(x+rangex[i], y+rangey[i]);
103 return true; //keep the chain going
104 }
105 }
106 else if (board[x+rangex[i]][y+rangey[i]] == opposite(check))// || board[x+rangex[i]][y+rangey[i]] == bad_spot )
107 return true;
108 }
109 return false;
110 }
111
112 void floodfill_bad(int x, int y)
113 {
114 for (int i = 0; i < 4; ++i)
115 {
116 if (board[x+rangex[i]][y+rangey[i]] == black_num ||
117 board[x+rangex[i]][y+rangey[i]] == white_num ||
118 board[x+rangex[i]][y+rangey[i]] == empty)
119 {
120 board[x+rangex[i]][y+rangey[i]] = bad_spot;
121 //floodfill again
122 floodfill_bad(x+rangex[i], y+rangey[i]);
123 }
124 }
125 }
126
127 int main()
128 {
129 int num_sets = 0;
130 int total_white = 0;
131 int total_black = 0;
132 scanf("%d%*[ \n\t]", &num_sets);
133 while (num_sets-- > 0)
134 {
135 getInput();
136
137 //count total pieces
138 for (int i = 1; i < LENGTH-1; ++i)
139 for (int j = 1; j < WIDTH-1; ++j)
140 if (board[i][j] == black)
141 total_black++;
142 else if (board[i][j] == white)
143 total_white++;
144 debug(total_black, endl);
145 debug(total_white, endl);
146 //dump();
147
148 //fill territories
149 for (int i = 1; i < LENGTH-1; ++i)
150 {
151 for (int j = 1; j < WIDTH-1; ++j)
152 {
153 debug(board[i][j], "");
154 if (board[i][j] == black)
155 floodfill(i, j, black);
156 else if (board[i][j] == white)// and total_white != 1)
157 floodfill(i, j, white);
158 }
159 }
160
161 dump();
162
163 //fill adjacent bad spots
164 for (int i = 1; i < LENGTH-1; ++i)
165 {
166 for (int j = 1; j < WIDTH-1; ++j)
167 {
168 debug(board[i][j], "");
169 if (board[i][j] == bad_spot)
170 floodfill_bad(i, j);
171 }
172 }
173 dump();
174
175
176 for (int i = 1; i < LENGTH-1; ++i)
177 {
178 for (int j = 1; j < WIDTH-1; ++j)
179 {
180 debug(board[i][j], "");
181 if (board[i][j] == black)
182 floodfill(i, j, black);
183 else if (board[i][j] == white)// and total_white != 1)
184 floodfill(i, j, white);
185 }
186 }
187 dump();
188 //count again
189
190 for (int i = 1; i < LENGTH-1; ++i)
191 for (int j = 1; j < WIDTH-1; ++j)
192 if (board[i][j] == black_num)
193 total_black++;
194 else if (board[i][j] == white_num)
195 total_white++;
196
197 printf("Black %d White %d\n", total_black, total_white);
198
199 //clear board, totals
200 CL2D(board, 0, LENGTH, WIDTH);
201 total_white = total_black = 0;
202 }
203
204 return 0;
205 }
206