#2325312

Solution for 0531: Paint Color by olphe

Source Code Status Test Cases
    Policy: public     Reviewed: 8    
00.00 sec    7072 KB    129 lines     2547 bytes    2017-05-19 07:12
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int H, W;
list<long long int>ans;
int dir[5] = { 1,0,-1,0,1 };

int main() {
	ios::sync_with_stdio(false);
	cin >> W >> H;
	while (H) {
		int N;
		vector<int>x;
		vector<int>y;
		set<int>xbox;
		set<int>ybox;
		vector<int>xzip;
		vector<int>yzip;
		bool field[2005][2005] = {};
		cin >> N;
		for (int i = 0; i < N; i++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			x.push_back(a);
			y.push_back(b);
			x.push_back(c);
			y.push_back(d);
			xbox.insert(a);
			xbox.insert(c);
			ybox.insert(b);
			ybox.insert(d);
		}
		xbox.insert(-1);
		xbox.insert(W);
		xbox.insert(0);
		ybox.insert(-1);
		ybox.insert(H);
		ybox.insert(0);
		for (auto i : xbox) {
			xzip.push_back(i);
		}
		for (auto i : ybox) {
			yzip.push_back(i);
		}
		for (int i = 0; i < N * 2; i++) {
			for (int j = 0; j < xzip.size(); j++) {
				if (x[i] == xzip[j]) {
					x[i] = j;
					break;
				}
			}
		}
		for (int i = 0; i < N * 2; i++) {
			for (int j = 0; j < yzip.size(); j++) {
				if (y[i] == yzip[j]) {
					y[i] = j;
					break;
				}
			}
		}
		for (int i = 1; i < yzip.size()-1; i++) {
			for (int j = 1; j < xzip.size()-1; j++) {
				field[i][j] = true;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = y[i * 2]; j < y[i * 2 + 1];j++) {
				for (int k = x[i * 2]; k < x[i * 2 + 1]; k++) {
					field[j][k] = false;
				}
			}
		}

		/*for (int i = yzip.size(); i >= 0; i--) {
			for (int j = 0; j < xzip.size(); j++) {
				if (field[i][j])cout << '.';
				else cout << '#';
			}
			cout << endl;
		}*/

		//cout << yzip.size() << endl;
		//cout << xzip.size() << endl;

		int box = 0;
		for (int i = 1; i < yzip.size(); i++) {
			for (int j = 1; j < xzip.size(); j++) {
				if (field[i][j]) {
					box++;
					queue<int>Q;
					field[i][j] = false;
					Q.push(i * 10000 + j);
					while (!Q.empty()) {
						int cy = Q.front()/10000;
						int cx = Q.front()%10000;
						for (int k = 0; k < 4; k++) {
							if (field[cy + dir[k]][cx + dir[k + 1]]) {
								Q.push((cy + dir[k]) * 10000 + cx + dir[k + 1]);
								field[cy + dir[k]][cx + dir[k + 1]] = false;
							}
						}
						Q.pop();
					}
				}
			}
		}
		ans.push_back(box);
		cin >> W >> H;
	}
	for (auto i : ans)cout << i << endl;
	return 0;
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++14 CPU: 00.00 sec Memory: 7072 KB Length: 2547 B 2017-05-19 07:12 2017-05-19 07:12
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 7072 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags