結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 colorislands[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;}