結果

問題 No.307 最近色塗る問題多くない?
ユーザー TatamoTatamo
提出日時 2016-03-02 01:57:14
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 60 ms / 4,000 ms
コード長 3,964 bytes
コンパイル時間 633 ms
コンパイル使用メモリ 65,028 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-11-21 22:16:10
合計ジャッジ時間 2,248 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
using namespace std;
/*
// 使!!1
*/
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0