結果

問題 No.307 最近色塗る問題多くない？
ユーザー __tatamo____tatamo__
提出日時 2016-03-02 01:45:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 59 ms / 4,000 ms
コード長 2,908 bytes
コンパイル時間 578 ms
コンパイル使用メモリ 66,000 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-11-21 22:15:50
合計ジャッジ時間 2,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 15 ms
5,248 KB
testcase_09 AC 8 ms
5,248 KB
testcase_10 AC 4 ms
5,248 KB
testcase_11 AC 8 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 12 ms
5,248 KB
testcase_14 AC 3 ms
5,248 KB
testcase_15 AC 3 ms
5,248 KB
testcase_16 AC 3 ms
5,248 KB
testcase_17 AC 7 ms
5,248 KB
testcase_18 AC 13 ms
5,760 KB
testcase_19 AC 15 ms
6,272 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 21 ms
8,576 KB
testcase_22 AC 46 ms
8,320 KB
testcase_23 AC 20 ms
8,576 KB
testcase_24 AC 20 ms
8,576 KB
testcase_25 AC 31 ms
9,088 KB
testcase_26 AC 34 ms
9,344 KB
testcase_27 AC 26 ms
9,600 KB
testcase_28 AC 59 ms
11,136 KB
testcase_29 AC 10 ms
5,248 KB
testcase_30 AC 32 ms
9,472 KB
testcase_31 AC 31 ms
9,984 KB
testcase_32 AC 29 ms
9,344 KB
testcase_33 AC 9 ms
5,248 KB
testcase_34 AC 20 ms
5,760 KB
testcase_35 AC 21 ms
5,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>

using namespace std;

struct Query{
	int r;
	int c;
	int x;
};
class Island;

int h, w;
int **a;
Island*** islands;

class Island{
	private:
		Island* parent;
		void init(int y, int x){
			if(y<0 || x < 0 || y >= h || x >= w) return;
			if(islands[y][x] == this) return;
			if(a[y][x] != color) {
				if(islands[y][x] != NULL){
					setJoinedIsland(islands[y][x]);
				}
				return;
			}
			islands[y][x] = this;
			init(y-1,x);
			init(y,x-1);
			init(y+1,x);
			init(y,x+1);
		}
	public:
		vector<Island*> childs;
		vector<Island*> joined_islands;
		int id;
		int color;
		Island(int y,int x,int id){
			this->id = id;
			parent = NULL;
			color = a[y][x];
			init(y,x);
		}
		void setJoinedIsland(Island* island){
			for(int i=0; i<joined_islands.size(); i++){
				if(joined_islands[i] == island) return; 
			}
			joined_islands.push_back(island);
			island->setJoinedIsland(this);
		}
		void setParent(Island *p){
			getParent()->parent = p;
			parent = p;
		}
		Island* getParent(){
			if(parent == NULL) return this;
			return parent = parent->getParent();
		}
		int getColor(){
			return getParent()->color;
		}
		void reverseColor(){
			if(parent!=NULL) {
				getParent()->reverseColor();
				return;
			}
			color = (color+1)%2;
			merge();
		}
		void merge(){
			if(joined_islands.size()>0){
				Island* p = getParent();
				for(int i=0;i<joined_islands.size();i++){
					Island* target = joined_islands[i]->getParent();
					if(target == p) continue;
					bool flg = true;
					for(int ii=0;ii<p->childs.size();ii++){
						if(p->childs[ii] == target) flg = false;
					}
					
					if(flg) {
						p->childs.push_back(target);
						target->setParent(p);
					}
				}
				joined_islands.clear();
			}
			else{
				vector<Island*> tmp = childs;
				childs.clear();
				for(int i=0;i<tmp.size();i++){
					tmp[i]->merge();
				}
			}
		}
};


int main(){
	ios::sync_with_stdio(false);
	cin >> h >> w;
	a = new int*[h];
	islands = new Island**[h];
	for(int i=0;i<h;i++){
		a[i] = new int[w];
		islands[i] = new Island*[w];
	}
	for(int i=0;i<h;i++){
		for(int ii=0;ii<w;ii++){
			cin >> a[i][ii];
			islands[i][ii] = NULL;
		}
	}
	int q;
	cin >> q;
	Query* qa = new Query[q];
	for(int i=0; i<q; i++){
		cin >> qa[i].r >> qa[i].c >> qa[i].x;
		qa[i].r -= 1;
		qa[i].c -= 1;
	}

	//cout << "all query loaded." << endl;

	int c=0;
	for(int i=0;i<h;i++){
		for(int ii=0;ii<w;ii++){
			if(islands[i][ii] == NULL){
				new Island(i,ii,c++);
			}
		}
	}
	//cout << "all Islands generated." << endl;

	for(int i=0;i<q;i++){
		Query query = qa[i];
		if(islands[query.r][query.c]->getColor() == query.x) continue; // same color
		islands[query.r][query.c]->reverseColor();

	}
	//cout << "all query completed." << endl;

	for(int i=0;i<h;i++){
		for(int ii=0;ii<w;ii++){
			cout << islands[i][ii]->getColor() << " ";
		}
		cout << endl;
	}

	//cout << "solved." << endl;
}
0