topcoder/GrafixMask.cpp at master · arshdeep/topcoder · GitHub

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include<climits>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
#include<set>
#include<queue>
#include<iterator>
#include<sstream>
#include<cassert>
#include<stack>
usingnamespacestd;
/*grafixMask : http://community.topcoder.com/stat?c=problem_statement&pm=2998&rd=5857 */
#defineHEIGHT400
#defineWIDTH600

structPoint
{
int x;
int y;
Point(int left, int top) : x(left), y(top) {}
};

structRectangle
{
Rectangle(const Point& _ul, const Point& _br)
 : ul(_ul), br(_br)
 {}

 Point ul;
 Point br;
};

typedef stack<Point> DfsSearch;
typedef queue<Point> BfsSearch;
typedef vector<Rectangle> Rectangles;

intdoFill(vector<vector<int>> &grafixMask, int left, int top, int right, int bottom)
{
	DfsSearch dfs;

	dfs.push(Point(left, top));
int count = 0;
while (!dfs.empty())
	{
 Point cp = dfs.top();

 dfs.pop();

if ((cp.x < 0 || cp.x >= WIDTH)
 || (cp.y < 0 || cp.y >= HEIGHT)
 || grafixMask[cp.x][cp.y]) {
continue;
 }

 ++count;
 grafixMask[cp.x][cp.y] = 1;
 dfs.push(Point(cp.x + 1, cp.y));
 dfs.push(Point(cp.x - 1, cp.y));
 dfs.push(Point(cp.x, cp.y + 1));
 dfs.push(Point(cp.x, cp.y - 1));
	}

return count;
}
voidmaskRect(vector<vector<int>> &grafixMask, Rectangle rect)
{
int top = rect.ul.y;
int left = rect.ul.x;
int bottom = rect.br.y;
int right = rect.br.x;

for (int idx = left; idx <= right; ++idx)
	{
for (int idy = top; idy <= bottom; ++idy)
 {
 grafixMask[idx][idy] = 1;
 }
	}
}

vector<int> sortedAreas(Rectangles& rectangles)
{
	vector<vector<int>> grafixMask(WIDTH, vector<int>(HEIGHT));
	vector<int> minAreas;

for (size_t idx = 0, rectCount = rectangles.size(); idx< rectCount; ++idx)
	{
maskRect(grafixMask, rectangles[idx]);
	}

for (int idx = 0; idx < WIDTH; ++idx)
	{
for (int idy = 0; idy < HEIGHT; ++idy)
 {
if (grafixMask[idx][idy] == 0)
 {
 minAreas.push_back(doFill(grafixMask, idx, idy, WIDTH, HEIGHT));
 }
 }
	}

std::sort(minAreas.begin(), minAreas.end());
return minAreas;
}

voidconvert(const vector<string>& strRectangles,
	Rectangles& rectangles) {
int upper; int left;
int bottom; int right;

for (size_t idx = 0; idx < strRectangles.size(); ++ idx)
	{
 istringstream iss(strRectangles[idx]);
if ( (iss >> upper) && (iss >> left) && (iss >> bottom) && (iss >> right) )
 {
 rectangles.push_back( Rectangle(Point(left, upper),
Point(right, bottom)) );
 }
	}
}

intmain(int argc, char *argv[])
{
	vector<string> strRectangles;
//test case {"0 292 399 307"}

/*strRectangles.push_back("48 192 351 207");
	strRectangles.push_back("48 392 351 407");
	strRectangles.push_back("120 52 135 547");
	strRectangles.push_back("260 52 275 547");*/
//Test case 2
/*strRectangles.push_back("0 192 399 207");
 strRectangles.push_back("0 392 399 407");
 strRectangles.push_back("120 0 135 599");
 strRectangles.push_back("260 0 275 599");*/
// TEST case 3
	strRectangles.push_back("0 20 399 20");
 strRectangles.push_back("0 44 399 44");
 strRectangles.push_back("0 68 399 68");
 strRectangles.push_back("0 92 399 92");
 strRectangles.push_back("0 116 399 116");
 strRectangles.push_back("0 140 399 140");
 strRectangles.push_back("0 164 399 164");
 strRectangles.push_back("0 188 399 188");
 strRectangles.push_back("0 212 399 212");
 strRectangles.push_back("0 236 399 236");
 strRectangles.push_back("0 260 399 260");
 strRectangles.push_back("0 284 399 284");
 strRectangles.push_back("0 308 399 308");
 strRectangles.push_back("0 332 399 332");
 strRectangles.push_back("0 356 399 356");
 strRectangles.push_back("0 380 399 380");
 strRectangles.push_back("0 404 399 404");
 strRectangles.push_back("0 428 399 428");
 strRectangles.push_back("0 452 399 452");
 strRectangles.push_back("0 476 399 476");
 strRectangles.push_back("0 500 399 500");
 strRectangles.push_back("0 524 399 524");
 strRectangles.push_back("0 548 399 548");
 strRectangles.push_back("0 572 399 572");
 strRectangles.push_back("0 596 399 596");
 strRectangles.push_back("5 0 5 599");
 strRectangles.push_back("21 0 21 599");
 strRectangles.push_back("37 0 37 599");
 strRectangles.push_back("53 0 53 599");
 strRectangles.push_back("69 0 69 599");
 strRectangles.push_back("85 0 85 599");
 strRectangles.push_back("101 0 101 599");
 strRectangles.push_back("117 0 117 599");
 strRectangles.push_back("133 0 133 599");
 strRectangles.push_back("149 0 149 599");
 strRectangles.push_back("165 0 165 599");
 strRectangles.push_back("181 0 181 599");
 strRectangles.push_back("197 0 197 599");
 strRectangles.push_back("213 0 213 599");
 strRectangles.push_back("229 0 229 599");
 strRectangles.push_back("245 0 245 599");
 strRectangles.push_back("261 0 261 599");
 strRectangles.push_back("277 0 277 599");
 strRectangles.push_back("293 0 293 599");
 strRectangles.push_back("309 0 309 599");
 strRectangles.push_back("325 0 325 599");
 strRectangles.push_back("341 0 341 599");
 strRectangles.push_back("357 0 357 599");
 strRectangles.push_back("373 0 373 599");
 strRectangles.push_back("389 0 389 599");

	Rectangles intRectangles;
convert(strRectangles, intRectangles);

	vector<int> minAreas = sortedAreas(intRectangles);

for (size_t idx = 0; idx < minAreas.size(); ++ idx)
	{
 cout<<minAreas[idx]<<"";
	}

getchar();
return0;
}