結果

問題 No.307 最近色塗る問題多くない？
コンテスト
ユーザー Tatamo
提出日時 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;
}
0