#include using namespace std; using ll = long long; const int INF = (int)1e9 + 1001010; const ll llINF = (long long)4e18 + 22000020; const string endn = "\n"; template inline auto vector2(size_t i, size_t j, const T &init = T()) { return vector(i, vector(j, init)); } const string ELM_SEP = "", VEC_SEP = endn; template istream &operator>>(istream &i, vector &A) { for(auto &I : A) i >> I; return i; } template ostream &operator<<(ostream &o, const vector &A) { int i = A.size(); for(const auto &I : A) o << I << (--i ? ELM_SEP : ""); return o; } template ostream &operator<<(ostream &o, const vector> &A) { int i = A.size(); for(const auto &I : A) o << I << (--i ? VEC_SEP : ""); return o; } template vector &operator++(vector &A, int) { for(auto &I : A) I++; return A; } template vector &operator--(vector &A, int) { for(auto &I : A) I--; return A; } template bool chmax(T &a, const U &b) { return ((a < b) ? (a = b, true) : false); } template bool chmin(T &a, const U &b) { return ((a > b) ? (a = b, true) : false); } ll floor(ll a, ll b) { if(b < 0) a = -a, b = -b; return (a >= 0) ? a / b : (a + 1) / b - 1; } ll ceil(ll a, ll b) { if(b < 0) a = -a, b = -b; return (a > 0) ? (a - 1) / b + 1 : a / b; } ll check_bit(unsigned long long val, unsigned long long digit) { return (val >> digit) & 1; } #ifdef DEBUG #include #define dump(...) cpp_dump(__VA_ARGS__) namespace cp = cpp_dump; struct InitCppDump { InitCppDump() { if(!isatty(fileno(stderr))) CPP_DUMP_SET_OPTION(es_style, cpp_dump::types::es_style_t::no_es); CPP_DUMP_SET_OPTION(log_label_func, cp::log_label::line()); CPP_DUMP_SET_OPTION(max_iteration_count, 30); } } init_cpp_dump; #else #define dump(...) #endif // ==================== ここまでテンプレ ==================== // (path compression) + (union by size) // 参考 AtCoder Library // == ACLからの変更点 == // group_num() を追加 // size関数をsize_of_group関数に改名 // groups() の返り値が昇順にソート済みであることを保証 class DSU{ int n; int _group_num; vector parent_or_size; public: explicit DSU(size_t n) : n(n), _group_num(n), parent_or_size(n, -1) {} // 頂点u, vを結合し、それらの新たなリーダーを返す // O(α(N)) int merge(int u, int v){ assert(0 <= u && u < n); assert(0 <= v && v < n); u = leader(u); v = leader(v); if(u == v) return u; if(-parent_or_size[u] < -parent_or_size[v]) swap(u, v); // make size(u) >= size(v) parent_or_size[u] += parent_or_size[v]; parent_or_size[v] = u; _group_num--; return u; } // 頂点u, vが同じ連結成分に属するかを判定する // O(α(N)) bool same(int u, int v){ assert(0 <= u && u < n); assert(0 <= v && v < n); return leader(u) == leader(v); } // 頂点vが属する連結成分の代表を返す // O(α(N)) int leader(int v){ assert(0 <= v && v < n); if(parent_or_size[v] < 0) return v; else return parent_or_size[v] = leader(parent_or_size[v]); } // 頂点vが属する連結成分のサイズを返す // O(α(N)) int size_of_group(int v){ assert(0 <= v && v < n); return -parent_or_size[leader(v)]; } // 連結成分の個数を返す // 返り値は groups().size()に等しい // O(1) int group_num(){ return _group_num; } // 連結成分ごとの頂点情報を返す // 1次元目、2次元目ともに昇順でソート済み // O(N) vector> groups(){ vector> result; // 頂点iをリーダーとする連結成分がresultに格納されるときのインデックス vector resultIndex(n, -1); for(int i = 0; i < n; i++){ int ld = leader(i); if(resultIndex[ld] == -1){ // resultIndex が未定のとき resultIndex[ld] = result.size(); result.emplace_back(); result.back().reserve(size_of_group(ld)); } result[resultIndex[ld]].emplace_back(i); } return result; } }; int main(int argc, char *argv[]){ ios::sync_with_stdio(false); cin.tie(nullptr); ll h, w; cin >> h >> w; auto g = vector2(h, w); cin >> g; DSU dsu(h * w); auto idx = [&](ll i, ll j) -> ll { return i * w + j; }; // merge for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(i < h-1){ if(g[i][j] == g[i+1][j]){ dsu.merge(idx(i, j), idx(i+1, j)); } } if(j < w-1){ if(g[i][j] == g[i][j+1]){ dsu.merge(idx(i, j), idx(i, j+1)); } } } } for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ if(dsu.size_of_group(idx(i, j)) >= 4){ g[i][j] = '.'; } } } cout << g << endl; return 0; }