#ifndef UNIONFIND_HPP #define UNIONFIND_HPP 1 #include namespace kk2 { struct UnionFind { std::vector d; UnionFind(int n = 0) : d(n, -1) {} bool same(int x, int y) { return find(x) == find(y); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (d[x] > d[y]) std::swap(x, y); d[x] += d[y]; d[y] = x; return true; } int find(int x) { if (d[x] < 0) return x; return d[x] = find(d[x]); } int size(int x) { return -d[find(x)]; } }; } // namespace kk2 #endif // UNIONFIND_HPP // #include #ifndef TEMPLATE #define TEMPLATE 1 // #pragma GCC optimize("O3,unroll-loops") // #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifndef TYPE_TRAITS_HPP #define TYPE_TRAITS_HPP 1 #include #include #include namespace kk2 { template using is_signed_int128 = typename std::conditional::value or std::is_same::value, std::true_type, std::false_type>::type; template using is_unsigned_int128 = typename std::conditional::value or std::is_same::value, std::true_type, std::false_type>::type; template using is_integral = typename std::conditional::value or is_signed_int128::value or is_unsigned_int128::value, std::true_type, std::false_type>::type; template using is_signed = typename std::conditional::value or is_signed_int128::value, std::true_type, std::false_type>::type; template using is_unsigned = typename std::conditional::value or is_unsigned_int128::value, std::true_type, std::false_type>::type; template using make_unsigned_int128 = typename std::conditional::value, __uint128_t, unsigned __int128>; template using to_unsigned = typename std::conditional::value, make_unsigned_int128, typename std::conditional::value, std::make_unsigned, std::common_type>::type>::type; template using is_integral_t = std::enable_if_t::value>; template using is_signed_t = std::enable_if_t::value>; template using is_unsigned_t = std::enable_if_t::value>; template using is_function_pointer = typename std::conditional && std::is_function_v>, std::true_type, std::false_type>::type; template ::value> * = nullptr> struct is_two_args_function_pointer : std::false_type {}; template struct is_two_args_function_pointer : std::true_type {}; template using is_two_args_function_pointer_t = std::enable_if_t::value>; namespace type_traits { struct istream_tag {}; struct ostream_tag {}; } // namespace type_traits template using is_standard_istream = std::is_same; template using is_standard_ostream = std::is_same; template using is_user_defined_istream = std::is_base_of; template using is_user_defined_ostream = std::is_base_of; template using is_istream = typename std::conditional::value || is_user_defined_istream::value, std::true_type, std::false_type>::type; template using is_ostream = typename std::conditional::value || is_user_defined_ostream::value, std::true_type, std::false_type>::type; template using is_istream_t = std::enable_if_t::value>; template using is_ostream_t = std::enable_if_t::value>; } // namespace kk2 #endif // TYPE_TRAITS_HPP // #include "../type_traits/type_traits.hpp" #ifndef TEMPLATE_FASTIO_HPP #define TEMPLATE_FASTIO_HPP 1 #include #include #include #include #include #include // #include "../type_traits/type_traits.hpp" namespace kk2 { namespace fastio { #define INPUT_FILE "in.txt" #define OUTPUT_FILE "out.txt" struct Scanner : type_traits::istream_tag { private: static constexpr size_t INPUT_BUF = 1 << 17; size_t pos = 0, end = 0; static char buf[INPUT_BUF]; FILE *fp; public: Scanner() : fp(stdin) {} Scanner(const char *file) : fp(fopen(file, "r")) {} ~Scanner() { if (fp != stdin) fclose(fp); } char now() { if (pos == end) { while (!(end = fread(buf, 1, INPUT_BUF, fp))) {} if (end != INPUT_BUF) buf[end] = '\0'; pos = 0; } return buf[pos]; } void skip_space() { while (isspace(now())) ++pos; } template * = nullptr> T next_unsigned_integral() { skip_space(); T res{}; while (isdigit(now())) { res = res * 10 + (now() - '0'); ++pos; } return res; } template * = nullptr> T next_signed_integral() { skip_space(); if (now() == '-') { ++pos; return T(-next_unsigned_integral::type>()); } else return (T)next_unsigned_integral::type>(); } char next_char() { skip_space(); auto res = now(); ++pos; return res; } std::string next_string() { skip_space(); std::string res; while (true) { char c = now(); if (isspace(c) or c == '\0') break; res.push_back(now()); ++pos; } return res; } template * = nullptr> Scanner &operator>>(T &x) { x = next_unsigned_integral(); return *this; } template * = nullptr> Scanner &operator>>(T &x) { x = next_signed_integral(); return *this; } Scanner &operator>>(char &x) { x = next_char(); return *this; } Scanner &operator>>(std::string &x) { x = next_string(); return *this; } }; struct endl_struct_t {}; struct Printer : type_traits::ostream_tag { private: static char helper[10000][5]; static char leading_zero[10000][5]; constexpr static size_t OUTPUT_BUF = 1 << 17; static char buf[OUTPUT_BUF]; size_t pos = 0; FILE *fp; template static constexpr void div_mod(T &a, T &b, T mod) { a = b / mod; b -= a * mod; } static void init() { buf[0] = '\0'; for (size_t i = 0; i < 10000; ++i) { leading_zero[i][0] = i / 1000 + '0'; leading_zero[i][1] = i / 100 % 10 + '0'; leading_zero[i][2] = i / 10 % 10 + '0'; leading_zero[i][3] = i % 10 + '0'; leading_zero[i][4] = '\0'; size_t j = 0; if (i >= 1000) helper[i][j++] = i / 1000 + '0'; if (i >= 100) helper[i][j++] = i / 100 % 10 + '0'; if (i >= 10) helper[i][j++] = i / 10 % 10 + '0'; helper[i][j++] = i % 10 + '0'; helper[i][j] = '\0'; } } public: Printer() : fp(stdout) { init(); } Printer(const char *file) : fp(fopen(file, "w")) { init(); } ~Printer() { write(); if (fp != stdout) fclose(fp); } void write() { fwrite(buf, 1, pos, fp); pos = 0; } void flush() { write(); fflush(fp); } void put_char(char c) { if (pos == OUTPUT_BUF) write(); buf[pos++] = c; } void put_cstr(const char *s) { while (*s) put_char(*(s++)); } void put_u32(uint32_t x) { uint32_t y; if (x >= 100000000) { // 10^8 div_mod(y, x, 100000000); put_cstr(helper[y]); div_mod(y, x, 10000); put_cstr(leading_zero[y]); put_cstr(leading_zero[x]); } else if (x >= 10000) { // 10^4 div_mod(y, x, 10000); put_cstr(helper[y]); put_cstr(leading_zero[x]); } else put_cstr(helper[x]); } void put_i32(int32_t x) { if (x < 0) { put_char('-'); put_u32(-x); } else put_u32(x); } void put_u64(uint64_t x) { uint64_t y; if (x >= 1000000000000ull) { // 10^12 div_mod(y, x, 1000000000000ull); put_u32(y); div_mod(y, x, 100000000ull); put_cstr(leading_zero[y]); div_mod(y, x, 10000ull); put_cstr(leading_zero[y]); put_cstr(leading_zero[x]); } else if (x >= 10000ull) { // 10^4 div_mod(y, x, 10000ull); put_u32(y); put_cstr(leading_zero[x]); } else put_cstr(helper[x]); } void put_i64(int64_t x) { if (x < 0) { put_char('-'); put_u64(-x); } else put_u64(x); } void put_u128(__uint128_t x) { constexpr static __uint128_t pow10_10 = 10000000000ull; constexpr static __uint128_t pow10_20 = pow10_10 * pow10_10; __uint128_t y; if (x >= pow10_20) { // 10^20 div_mod<__uint128_t>(y, x, pow10_20); put_u64(uint64_t(y)); div_mod<__uint128_t>(y, x, __uint128_t(10000000000000000ull)); put_cstr(leading_zero[y]); div_mod<__uint128_t>(y, x, __uint128_t(1000000000000ull)); put_cstr(leading_zero[y]); div_mod<__uint128_t>(y, x, __uint128_t(100000000ull)); put_cstr(leading_zero[y]); div_mod<__uint128_t>(y, x, __uint128_t(10000ull)); put_cstr(leading_zero[y]); put_cstr(leading_zero[x]); } else if (x >= __uint128_t(10000)) { // 10^4 div_mod<__uint128_t>(y, x, __uint128_t(10000)); put_u64(uint64_t(y)); put_cstr(leading_zero[x]); } else put_cstr(helper[x]); } void put_i128(__int128_t x) { if (x < 0) { put_char('-'); put_u128(-x); } else put_u128(x); } template * = nullptr> Printer &operator<<(T x) { if constexpr (sizeof(T) <= 4) put_u32(x); else if constexpr (sizeof(T) <= 8) put_u64(x); else put_u128(x); return *this; } template * = nullptr> Printer &operator<<(T x) { if constexpr (sizeof(T) <= 4) put_i32(x); else if constexpr (sizeof(T) <= 8) put_i64(x); else put_i128(x); return *this; } Printer &operator<<(char x) { put_char(x); return *this; } Printer &operator<<(const std::string &x) { for (char c : x) put_char(c); return *this; } Printer &operator<<(const char *x) { put_cstr(x); return *this; } // std::cout << std::endl; は関数ポインタを渡しているらしい Printer &operator<<(endl_struct_t) { put_char('\n'); flush(); return *this; } }; char Scanner::buf[Scanner::INPUT_BUF]; char Printer::buf[Printer::OUTPUT_BUF]; char Printer::helper[10000][5]; char Printer::leading_zero[10000][5]; } // namespace fastio #if defined(INTERACTIVE) || defined(USE_STDIO) auto &kin = std::cin; auto &kout = std::cout; auto (*kendl)(std::ostream &) = std::endl>; #elif defined(KK2) fastio::Scanner kin(INPUT_FILE); fastio::Printer kout(OUTPUT_FILE); fastio::endl_struct_t kendl; #else fastio::Scanner kin; fastio::Printer kout; fastio::endl_struct_t kendl; #endif } // namespace kk2 #endif // TEMPLATE_FASTIO_HPP // #include "fastio.hpp" using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using pi = std::pair; using pl = std::pair; using pil = std::pair; using pli = std::pair; template using vc = std::vector; template using vvc = std::vector>; template using vvvc = std::vector>; template using vvvvc = std::vector>; template using pq = std::priority_queue; template using pqi = std::priority_queue, std::greater>; template constexpr T infty = 0; template <> constexpr int infty = (1 << 30) - 123; template <> constexpr i64 infty = (1ll << 62) - (1ll << 31); template <> constexpr i128 infty = (i128(1) << 126) - (i128(1) << 63); template <> constexpr u32 infty = infty; template <> constexpr u64 infty = infty; template <> constexpr u128 infty = infty; template <> constexpr double infty = infty; template <> constexpr long double infty = infty; constexpr int mod = 998244353; constexpr int modu = 1e9 + 7; constexpr long double PI = 3.14159265358979323846; namespace kk2 { template auto make_vector(int first, Sizes... sizes) { if constexpr (sizeof...(sizes) == 0) { return std::vector(first); } else { return std::vector(first, make_vector(sizes...)); } } template void fill_all(std::vector &v, const U &x) { std::fill(std::begin(v), std::end(v), T(x)); } template void fill_all(std::vector> &v, const U &x) { for (auto &u : v) fill_all(u, x); } } // namespace kk2 template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } #define rep1(a) for (i64 _ = 0; _ < (i64)(a); ++_) #define rep2(i, a) for (i64 i = 0; i < (i64)(a); ++i) #define rep3(i, a, b) for (i64 i = (a); i < (i64)(b); ++i) #define repi2(i, a) for (i64 i = (a) - 1; i >= 0; --i) #define repi3(i, a, b) for (i64 i = (a) - 1; i >= (i64)(b); --i) #define overload3(a, b, c, d, ...) d #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__) #define fi first #define se second #define all(p) std::begin(p), std::end(p) using kk2::kendl; using kk2::kin; using kk2::kout; struct IoSetUp { IoSetUp() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } } iosetup; template * = nullptr> OStream &operator<<(OStream &os, const std::pair &p) { os << p.first << ' ' << p.second; return os; } template * = nullptr> IStream &operator>>(IStream &is, std::pair &p) { is >> p.first >> p.second; return is; } template * = nullptr> OStream &operator<<(OStream &os, const std::vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == (int)v.size() ? "" : " "); } return os; } template * = nullptr> IStream &operator>>(IStream &is, std::vector &v) { for (auto &x : v) is >> x; return is; } void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); } void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); } void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); } void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); } void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); } void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); } #endif // TEMPLATE // #include using namespace std; void solve() { int h, w; kin >> h >> w; vc g(h); kin >> g; kk2::UnionFind uf(h * w); rep (i, h) rep (j, w) { if (g[i][j] == '.') continue; rep (d, 4) { int ni = i + "1012"[d] - '1'; int nj = j + "2101"[d] - '1'; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if (g[ni][nj] == g[i][j]) { uf.unite(i * w + j, ni * w + nj); } } } rep (i, h) rep (j, w) { if (uf.size(i * w + j) >= 4) g[i][j] = '.'; } for (auto v : g) kout << v << "\n"; } int main() { int t = 1; // kin >> t; rep (t) solve(); return 0; } // converted!!