結果

問題 No.307 最近色塗る問題多くない？
ユーザー satos___jpsatos___jp
提出日時 2015-11-27 23:46:50
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,736 bytes
コンパイル時間 1,065 ms
コンパイル使用メモリ 72,716 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2023-10-12 01:32:19
合計ジャッジ時間 5,662 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,500 KB
testcase_01 AC 3 ms
4,512 KB
testcase_02 AC 3 ms
4,508 KB
testcase_03 AC 3 ms
4,456 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,948 KB
testcase_11 AC 54 ms
5,124 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 4 ms
4,652 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 126 ms
6,508 KB
testcase_28 WA -
testcase_29 AC 175 ms
4,504 KB
testcase_30 WA -
testcase_31 AC 291 ms
6,516 KB
testcase_32 AC 276 ms
6,520 KB
testcase_33 AC 13 ms
5,120 KB
testcase_34 AC 235 ms
5,128 KB
testcase_35 AC 233 ms
5,120 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));
		y=np.fir; x=np.sec;
		//printf("np .. %d %d\n",np.fir,np.sec);
		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;
}


/*
4 4
1 0 1 1
0 1 0 0
0 0 1 1
1 0 1 0
3
3 1 1
2 1 1
1 1 0

*/
0