#include #include #include using namespace std; typedef pair ip; #define Y first #define X second struct Query{ int r; int c; int x; }; class Island; int h, w; int **a; Island*** islands; int counter = 0; class Island{ private: Island* parent; void init(int y, int x){ if(y<0 || x < 0 || y >= h || x >= w) return; for(int i=0; i < pos.size(); i++){ if(pos[i].X == x && pos[i].Y == y){ return; } } if(a[y][x] != color) { if(islands[y][x] != NULL){ setJoinedIsland(islands[y][x]); } return; } pos.push_back(ip(y,x)); islands[y][x] = this; init(y-1,x); init(y,x-1); init(y+1,x); init(y,x+1); } public: vector childs; vector joined_islands; vector pos; 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; isetJoinedIsland(this); } void setParent(Island *p){ getParent()->parent = p; parent = p; } Island* getParent(){ counter++; 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;igetParent(); if(target == p) continue; bool flg = true; for(int ii=0;iichilds.size();ii++){ if(p->childs[ii] == target) flg = false; } if(flg) { p->childs.push_back(target); target->setParent(p); } } joined_islands.clear(); } else{ vector tmp = childs; childs.clear(); for(int i=0;imerge(); } } } }; int main(){ ios::sync_with_stdio(false); cin >> h >> w; a = new int*[h]; islands = new Island**[h]; for(int i=0;i> a[i][ii]; islands[i][ii] = NULL; } } int q; cin >> q; Query* qa = new Query[q]; for(int i=0; i> qa[i].r >> qa[i].c >> qa[i].x; qa[i].r -= 1; qa[i].c -= 1; } int c=0; for(int i=0;igetColor() == query.x) continue; // same color islands[query.r][query.c]->reverseColor(); } for(int i=0;igetColor(); } } for(int i=0;igetColor() << " "; } cout << endl; } }