結果
問題 |
No.2946 Puyo
|
ユーザー |
|
提出日時 | 2024-11-10 02:39:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 1,292 ms |
コンパイル使用メモリ | 104,144 KB |
実行使用メモリ | 118,856 KB |
最終ジャッジ日時 | 2024-11-10 02:39:21 |
合計ジャッジ時間 | 8,795 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,a,n) for(int i=(a);i<(n);i++) //Union-Find struct UnionFind{ vector<int> par, rank, siz; UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {} int root(int x){ if(par[x] == -1) return x; else return par[x] = root(par[x]); } bool same(int x, int y){ return root(x) == root(y); } bool unite(int x, int y){ int rx = root(x), ry = root(y); if(rx == ry) return false; if(rank[rx] < rank[ry]) swap(rx, ry); par[ry] = rx; if(rank[rx] == rank[ry]) rank[rx]++; siz[rx] += siz[ry]; return true; } int size(int x) { return siz[root(x)]; } vector<vector<int>> group(){ vector<vector<int>> tmp(par.size()); for(int i = 0; i < (int)par.size(); i++) tmp[root(i)].push_back(i); vector<vector<int>> ans; for(vector<int> p : tmp) if(!p.empty()) ans.push_back(p); return ans; } }; int h, w; string g[1000]; int d[5] = {0, 1, 0, -1, 0}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> h >> w; UnionFind uf(h*w); for(int i=0; i<h; i++) cin >> g[i]; for(int i=0; i<h; i++) for(int j=0; j<w; j++){ for(int k=0; k<4; k++){ int x=i+d[k], y=j+d[k+1]; if(!(0<=x&&x<h&&0<=y&&y<w)) continue; if(g[i][j]==g[x][y]) uf.unite(i*w+j, x*w+y); } } for(vector<int> v : uf.group()){ if(v.size()<4) continue; for(int p : v) g[p/w][p%w] = '.'; } for(int i=0; i<h; i++) cout << g[i] << endl; }