#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_RUN
#include "debug_common.h"
#else
#define trace(...) ;
#define dbg(...) ;
#define dbgc(...) ;
#define debug(x) ;
#define debuga(a, n) ;
#define debug2(x, y) ;
#define debug3(x, y, z) ;
#define debug4(x, y, z, w) ;
#define debug5(a,b,c,d,e) ;
#define lassert(x) ;
#define dassert(x, ...) ;
int recur_depth = 0; bool rec_indent = true;
const bool isLocal = false;
#endif
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define all(v) begin(v), end(v)
#define rall(v) (v).rbegin(),(v).rend()
#define make_unique(v) (v).erase(unique(all(v)), (v).end())
#define sz(c) ((int) c.size())
#define forn(i,n) for(auto i=(n)-(n);i<(n);i++)
#define fornn(i,s,n) for(auto i=(n)-(n)+(s);i<(n);i++)
#define forb(i,n) for(auto i=(n)-1;i>=0;i--)
#define forbn(i,s,n) for(auto i=(n)-1;i>=(s);i--)
#define forbit(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define mem(a,b) memset(a,b,sizeof(a))
#define abs(x) (((x) < 0) ? -(x) : (x))
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(abs(x))
#define has(c,x) (c.find(x) != c.end())
#define pw(x) (1LL << (x))
#define ibit(x,i) (((x) >> (i)) & 1)
#define preturn(...) {out(__VA_ARGS__); return;}
#define data(v) v.data(), sz(v) // vi -> vai
#define gtime() ((double(clock()) - 0)/CLOCKS_PER_SEC)
typedef stringstream sstr;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef valarray<int> vai;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template<class F>
struct y_comb{
F f;
template<class T> explicit y_comb(T &&f_in): f(forward<T>(f_in)){ }
template<class ...Args> decltype(auto) operator()(Args &&...args){ return f(ref(*this), forward<Args>(args)...); }
};
template<class F>
decltype(auto) yf(F &&f){
return y_comb<decay_t<F>>(forward<F>(f));
}
inline int ni(){ int x; cin >> x; return x; }
inline ll nl() { ll x; cin >> x; return x; }
template <class T> void mmin(T& a, const T& b) {
a = (a) < (b) ? (a) : (b);
}
template <class T> void mmax(T& a, const T& b) {
a = (a) > (b) ? (a) : (b);
}
template <class T> int LB(vc<T> &a, T x){
return int(lower_bound(all(a), x) - a.begin());
}
template <class T> int UB(vc<T> &a, T x){
return int(upper_bound(all(a), x) - a.begin());
}
template <class T> T MAX(vc<T> &a, int l=0, int r=-1){
if(r < 0) r = sz(a);
return *max_element(a.begin()+l, a.begin()+r);
}
template <class T> T MIN(vc<T> &a, int l=0, int r=-1){
if(r < 0) r = sz(a);
return *min_element(a.begin()+l, a.begin()+r);
}
template <class T> auto vv(int d1, T x){
return vc<T>(d1, x);
}
template <class T> auto vv(int d1, int d2, T x){
return vc<vc<T>>(d1, vc<T>(d2, x));
}
template <class T> auto vv(int d1, int d2, int d3, T x){
return vc<vc<vc<T>>>(d1, vv(d2, d3, x));
}
template <class T> auto vv(int d1, int d2, int d3, int d4, T x){
return vc<vc<vc<vc<T>>>>(d1, vv(d2, d3, d4, x));
}
void outv(auto &v){
for(auto &x: v) {cout<< x <<" ";} cout<<endl;
}
void rvec(int &n, auto &v){
cin >> n; v.resize(n); for(auto &x: v) cin >> (x);
}
template<class T> istream& operator>> (istream& in, vector<T>& v) {
lassert(!v.empty()); for(T &x: v) cin >> x;
return in;
}
template <class Arg, class... Args>
void read(Arg&& arg, Args&&... args){
cin >> std::forward<Arg>(arg); using expander = int[];
(void)expander{0, (void(cin >> std::forward<Args>(args)),0)...};
}
template <class Arg, class... Args>
void out(Arg&& arg, Args&&... args){
cout << std::forward<Arg>(arg); using expander = int[];
(void)expander{0, (void(cout << " " << std::forward<Args>(args)),0)...};
cout << endl;
}
template <class Integer, class F>
Integer find_first_false(Integer l, Integer r, F&& f) {
--l; // ++r;
while (r - l > 1) {
Integer m = midpoint(l, r);
if (f(m)) l = m;
else r = m;
}
return r;
}
template <class Integer, class F>
Integer find_last_true(Integer l, Integer r, F &&f) {
return find_first_false(l, r, [&f](Integer i) { return f(i); }) - 1;
}
template <class Integer, class F>
Integer find_first_true(Integer l, Integer r, F &&f) {
return find_first_false(l, r, [&f](Integer i) { return !f(i); });
}
template <class T, class F>
T last_true(T lo, T hi, F&& f) {
lo--; // if all are false, return lo-1
while(lo < hi){
T mid = lo + (hi - lo + 1) / 2;
if(f(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
template <class T, class F>
T first_true(T lo, T hi, F&& f) {
// return last_true(lo, hi, [&](T x){ return !f(x); }) + 1;
hi++; // if all are false, return hi+1
while(lo < hi){
T mid = lo + (hi - lo) / 2;
if(f(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
ll pwr(ll base, ll p, ll mod){
ll ans=1; while(p) {if(p&1) ans=(ans*base)%mod;
base=(base*base)%mod; p/=2;}
return ans;
}
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b,a%b); }
ll lcm(ll a, ll b) { return a*(b/gcd(a,b)); }
ll isqrt (ll x) {
ll ans = sqrt(x)+2; while(ans*ans>x) ans--;
return ans;
}
string yes(bool t = 1) { return t ? "YES" : "NO"; }
string no(bool t = 1) { return yes(!t); }
void pyes(bool t = 1) { out(yes(t)); }
void pno(bool t = 1) { out(no(t)); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long double PI = (long double)(3.1415926535897932384626433832795);
const ll mx_ll = numeric_limits<ll> :: max();
const int mx_int = numeric_limits<int> :: max();
const int oo = 0x3f3f3f3f;
const ll OO = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-9;
const int DX[8]={0,1, 0,-1,-1,1,-1, 1};
const int DY[8]={1,0,-1, 0,-1,1, 1,-1};
bool MULTIPLE_TESTS = 0;
const int maxn = 1e5 + 3;
const int mod = 1e9+7;
void _build(){}
struct UnionFind { // OOP style
int N; vi parent, siz;
UnionFind(int _N): N(_N) {
siz.assign(N, 1);
parent.assign(N, 0);
for (int i = 0; i < N; i++) parent[i] = i;
}
int find(int i) {
if(parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
bool same(int i, int j) { return find(i) == find(j); }
void merge(int i, int j) {
int a = find(i);
int b = find(j);
if (a != b) {
if (siz[a] > siz[b]) swap(a, b);
parent[a] = b;
siz[b] += siz[a];
}
}
int operator [] (int i) {
return find(i);
}
int size(int x) {
return siz[find(x)];
}
vvi gids(){
vvi gs(N);
forn(i, N) gs[find(i)].pb(i);
return gs;
}
map<int, vi> groups(){ // for debug
map<int, vi> groups;
forn(i, N) groups[find(i)].pb(i);
return groups;
}
};
void _solve(){
int n, m; cin >> n >> m;
auto g = vv(n, m, '.'); cin >> g;
auto id = vv(n, m, 0); forn(i, n) forn(j, m) id[i][j] = i*m + j;
int N = n*m;
UnionFind uf(N);
forn(x, n) forn(y, m) {
if(g[x][y] == '.') continue;
forn(k, 4) {
int nx = x + DX[k], ny = y + DY[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] != g[x][y]) continue;
uf.merge(id[x][y], id[nx][ny]);
}
}
// vvi groups = uf.gids();
vvi adj(N);
forn(x, n) forn(y, m) {
if(g[x][y] == '.') continue;
forn(k, 4) {
int nx = x + DX[k], ny = y + DY[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '.') continue;
if(g[x][y] == g[nx][ny]) continue;
int a = id[x][y], b = id[nx][ny];
adj[uf[a]].pb(uf[b]);
}
}
auto bfs = [&](int s) {
vi d(N, -1);
queue<int> q;
q.push(s);
d[s] = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int v: adj[u]) {
if(d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return MAX(d);
};
out(bfs(uf[0]) + 1);
}
/*************************************************************************/
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//cout.precision(15);
_build();
int num_tests=1;
if(MULTIPLE_TESTS) cin>>num_tests;
if(MULTIPLE_TESTS) debug(num_tests);
forn(i,num_tests){
_solve();
}
// return 0;
while(isspace(cin.peek())) cin.get();
while(cin.peek() != EOF){
_solve();
while(isspace(cin.peek())) cin.get();
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
