結果

問題 No.307 最近色塗る問題多くない？
ユーザー satos___jpsatos___jp
提出日時 2015-11-27 23:38:31
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,607 bytes
コンパイル時間 669 ms
コンパイル使用メモリ 73,116 KB
実行使用メモリ 7,332 KB
最終ジャッジ日時 2023-10-12 01:04:47
合計ジャッジ時間 5,149 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,428 KB
testcase_01 AC 3 ms
4,432 KB
testcase_02 AC 3 ms
4,400 KB
testcase_03 AC 3 ms
4,440 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 25 ms
4,860 KB
testcase_11 AC 55 ms
5,140 KB
testcase_12 WA -
testcase_13 AC 234 ms
4,576 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 4 ms
4,564 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 131 ms
6,480 KB
testcase_28 WA -
testcase_29 AC 172 ms
4,464 KB
testcase_30 WA -
testcase_31 AC 267 ms
6,496 KB
testcase_32 AC 252 ms
6,524 KB
testcase_33 WA -
testcase_34 AC 191 ms
5,088 KB
testcase_35 AC 192 ms
5,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX

int h,w;
int dat[205][205];
int gone[205][205];

int dd[5]={1,0,-1,0,1};


vector<mp> vs[205][205];


mp uni[205][205];

void init(){
	rep(y,205){
		rep(x,205){
			uni[y][x]=mp(y,x);
		}
	}
}

mp find(mp p){
	mp& np=uni[p.fir][p.sec];
	if(np==p)return p;
	return (np=find(np));
}

void mer(mp pa,mp pb){
	mp pp=find(pb);
	uni[pp.fir][pp.sec]=find(pa);
}

bool same(mp pa,mp pb){
	return find(pa)==find(pb);
}




	
int main(void){
	init();
	scanf("%d%d",&h,&w);
	reg(y,1,h){
		reg(x,1,w){
			scanf("%d",&dat[y][x]);
		}
	}
	
	reg(y,1,h){
		reg(x,1,w-1){
			if(dat[y][x]==dat[y][x+1])mer(mp(y,x),mp(y,x+1));
		}
	}
	
	reg(y,1,h-1){
		reg(x,1,w){
			if(dat[y][x]==dat[y+1][x])mer(mp(y+1,x),mp(y,x));
		}
	}

	
	reg(y,1,h){
		reg(x,1,w-1){
			if(dat[y][x]!=dat[y][x+1]){
				mp pa=find(mp(y,x));
				mp pb=find(mp(y,x+1));
				//printf("(%d %d) (%d %d)\n",pa.fir,pa.sec,pb.fir,pb.sec);
				vs[pa.fir][pa.sec].push_back(pb);
				vs[pb.fir][pb.sec].push_back(pa);
			}
		}
	}
	//printf("yo\n");
	reg(y,1,h-1){
		reg(x,1,w){
			if(dat[y][x]!=dat[y+1][x]){
				mp pa=find(mp(y,x));
				mp pb=find(mp(y+1,x));
				//printf("(%d %d) (%d %d)\n",pa.fir,pa.sec,pb.fir,pb.sec);
				vs[pa.fir][pa.sec].push_back(pb);
				vs[pb.fir][pb.sec].push_back(pa);
			}
		}
	}

	int qqq;
	scanf("%d",&qqq);
	rep(i,qqq){
		int y,x,c;
		scanf("%d%d%d",&y,&x,&c); 
		memset(gone,0,sizeof(gone));
		
		mp np=find(mp(y,x));
		if(dat[np.fir][np.sec]==c)continue;
		dat[np.fir][np.sec]=c;
		vector<mp> tvs;
		for(mp pa :vs[y][x]){
			//printf("rin %d %d\n",pa.fir,pa.sec);
			if(!same(np,pa)){
				mer(np,pa);
				/*
	reg(y,1,h){
		reg(x,1,w){
			mp pp=find(mp(y,x));
			printf("%d%c",dat[pp.fir][pp.sec],x==w?'\n':' ');
		}
	}
				*/
				for(mp pb :vs[pa.fir][pa.sec]){
					if(!same(np,pb))tvs.push_back(np);
				}
			}
		}
		swap(vs[y][x],tvs);
		/*
	reg(y,1,h){
		reg(x,1,w){
			mp pp=find(mp(y,x));
			printf("%d%c",dat[pp.fir][pp.sec],x==w?'\n':' ');
		}
	}*/
	}
	reg(y,1,h){
		reg(x,1,w){
			mp pp=find(mp(y,x));
			printf("%d%c",dat[pp.fir][pp.sec],x==w?'\n':' ');
		}
	}
	
	return 0;
}
0