結果

問題 No.307 最近色塗る問題多くない？
コンテスト
ユーザー __tatamo__
提出日時 2016-03-01 22:40:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,426 bytes
コンパイル時間 845 ms
コンパイル使用メモリ 66,112 KB
実行使用メモリ 814,336 KB
最終ジャッジ日時 2024-09-24 13:15:28
合計ジャッジ時間 3,002 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<utility>

using namespace std;

typedef pair<int,int> ip;
#define Y first
#define X second

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

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


class Island{
	private:
		void init(int y, int x){
			if(y<0 || x < 0 || y >= h || x >= w) return;
			for(int i=0; i < pos.size(); i++){
				if(pos[i].X == x && pos[i].Y == y){
					return;
				}
			}
			if(a[y][x] != color) {
				if(islands[y][x] != NULL){
					setJoinedIsland(islands[y][x]);
				}
				return;
			}
			pos.push_back(ip(y,x));
			islands[y][x] = this;
			init(y-1,x);
			init(y,x-1);
			init(y+1,x);
			init(y,x+1);
		}
	public:
		Island* parent;
		vector<Island*> childs;
		vector<Island*> joined_islands;
		vector<ip> pos;
		int color;
		int id;
		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){
			parent = p;
			color = p->color;
			for(int i=0;i<childs.size();i++){
				childs[i]->setParent(p);
			}
		}
		void reverseColor(){
			color = (color+1)%2;
			for(int i=0;i<joined_islands.size();i++){
				joined_islands[i]->setParent(this);
				childs.push_back(joined_islands[i]);
			}
			joined_islands.clear();
		}
};


int main(){
	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;
	}

	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++);
			}
		}
	}

	for(int i=0;i<q;i++){
		Query query = qa[i];
		if(a[query.r][query.c] == query.x) continue; // same color
		islands[query.r][query.c]->reverseColor();
	}
	for(int i=0;i<h;i++){
		for(int ii=0;ii<w;ii++){
			cout << islands[i][ii]->color << " ";
			/*for(int iii=0;iii<islands[i][ii]->joined_islands.size();iii++){
				cout << islands[i][ii]->joined_islands[iii]->id << ", ";
			}
			cout << endl;*/
		}
		cout << endl;
	}
}
0