#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
// use less_equal to make it multiset
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
typedef pair<double, double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int>> vv32;
typedef vector<vector<ll>> vv64;
typedef vector<vector<p64>> vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<pair<p64, ll>> vpp64;
typedef set<ll> s64;
typedef set<p64> sp64;
typedef multiset<ll> ms64;
typedef multiset<p64> msp64;
typedef map<ll, ll> m64;
typedef map<ll, v64> mv64;
typedef unordered_map<ll, v64> uv64;
typedef unordered_map<ll, ll> u64;
typedef unordered_map<p64, ll> up64;
typedef unordered_map<ll, vp64> uvp64;
typedef priority_queue<ll> pq64;
typedef priority_queue<ll, v64, greater<ll>> pqs64;
const int MOD = 1000000007;
double eps = 1e-12;
#define forn(i, n) for (ll i = 0; i < n; i++)
#define forsn(i, s, e) for (ll i = s; i < e; i++)
#define rforn(i, s) for (ll i = s; i >= 0; i--)
#define rforsn(i, s, e) for (ll i = s; i >= e; i--)
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(p64 x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM) ^ splitmix64(x.second + FIXED_RANDOM);
}
size_t operator()(ll x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef gp_hash_table<ll, ll, custom_hash> fm64;
typedef gp_hash_table<p64, ll, custom_hash> fmp64;
#define ln "\n"
#define mp make_pair
#define ie insert
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define al(arr, n) arr, arr + n
#define sz(x) ((ll)(x).size())
#define dbg(a) cout << a << endl;
#define dbg2(a) cout << a << ' ';
using ld = long double;
using db = double;
using str = string; // yay python!
// INPUT
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
tcT > void re(T &x)
{
cin >> x;
}
tcTUU > void re(T &t, U &...u)
{
re(t);
re(u...);
}
int find_set(int v, v64 &parent)
{
if (-1 == parent[v])
return v;
return parent[v] = find_set(parent[v], parent);
}
void union_sets(int a, int b, v64 &parent)
{
a = find_set(a, parent);
b = find_set(b, parent);
if (a != b)
parent[b] = a;
}
// function for prime factorization
vector<pair<ll, ll>> pf(ll n)
{
vector<pair<ll, ll>> prime;
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
int count = 0;
while (n % i == 0)
{
count++;
n = n / i;
}
prime.pb(mp(i, count));
}
}
if (n > 1)
{
prime.pb(mp(n, 1));
}
return prime;
}
// sum of digits of a number
ll sumofno(ll n)
{
ll sum = 0;
while (n != 0)
{
sum += n % 10;
n = n / 10;
}
return sum;
}
// modular exponentiation
long long modpow(long long x, long long n, long long p)
{
if (n == 0)
return 1 % p;
ll ans = 1, base = x;
while (n > 0)
{
if (n % 2 == 1)
{
ans = (ans * base) % p;
n--;
}
else
{
base = (base * base) % p;
n /= 2;
}
}
if (ans < 0)
ans = (ans + p) % p;
return ans;
}
// const int N = 1e6 + 100;
// long long fact[N];
// initialise the factorial
// void initfact(){
// fact[0] = 1;
// for (int i = 1; i < N; i++)
//{
// fact[i] = (fact[i - 1] * i);
// fact[i] %= MOD;
// }}
// formula for c
// ll C(ll n, ll i)
//{
// ll res = fact[n];
// ll div = fact[n - i] * fact[i];
// div %= MOD;
// div = modpow(div, MOD - 2, MOD);
// return (res * div) % MOD;
// }
long long CW(ll n, ll m)
{
if (m > n - m)
m = n - m;
long long ans = 1;
for (int i = 0; i < m; i++)
{
ans = ans * (n - i) / (i + 1);
}
return ans;
}
// function for fast expo
ll fastexpo(ll a, ll b)
{
if (b == 0)
{
return 1;
}
if (a == 0)
{
return 0;
}
ll y = fastexpo(a, b / 2);
if (b % 2 == 0)
{
return y * y;
}
else
{
return a * y * y;
}
}
ll popcount(ll n)
{
ll c = 0;
for (; n; ++c)
n &= n - 1;
return c;
}
ll ce(ll x, ll y)
{
ll res = x / y;
if (x % y != 0)
{
res++;
}
return res;
}
bool pow2(ll x)
{
ll res = x & (x - 1);
if (res == 0)
{
return true;
}
return false;
}
bool isPrime(int x)
{
for (int d = 2; d * d <= x; d++)
{
if (x % d == 0)
return false;
}
return true;
}
int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool isvalid(int x, int y)
{
if (x < 1 || x > n || y < 1 || y > m)
{
return false;
}
return true;
}
void solve()
{
cin >> n >> m;
vector<vector<char>> arr(n + 10, vector<char>(m + 10, '.'));
vv64 vis(n + 10, v64(m + 10));
vv64 dist(n + 10, v64(m + 10));
forsn(i, 1, n + 1)
{
forsn(j, 1, m + 1)
{
cin >> arr[i][j];
}
}
deque<p64> q;
q.push_back({1, 1});
vis[1][1] = 1;
dist[1][1] = 1;
ll ans = 0;
while (!q.empty())
{
ll x1 = q.front().first;
ll y1 = q.front().second;
ans = max(ans, dist[x1][y1]);
q.pop_front();
forn(i, 4)
{
ll X = x1 + dx[i];
ll Y = y1 + dy[i];
if (isvalid(X, Y) && arr[X][Y] != '.')
{
if (vis[X][Y] == 0)
{
vis[X][Y] = 1;
if (arr[x1][y1] == arr[X][Y])
{
dist[X][Y] = dist[x1][y1];
q.push_front({X, Y});
}
else
{
dist[X][Y] = dist[x1][y1] + 1;
q.push_back({X, Y});
}
}
}
}
}
cout << ans << ln;
}
int main()
{
fast_cin();
//#ifndef ONLINE_JUDGE
// freopen("revegetate.in", "r", stdin);
// freopen("revegetate.out", "w", stdout);
//#endif
ll t = 1;
// cin >> t;
for (int it = 1; it <= t; it++)
{
solve();
}
return 0;
}
/*
1. Check borderline constraints. Can a variable you are dividing by be 0?
2. Use ll while using bitshifts
3. Do not erase from set while iterating it
4. Initialise everything
5. Read the task carefully, is something unique, sorted, adjacent, guaranteed??
6. DO NOT use if(!mp[x]) if you want to iterate the map later
7. Are you using i in all loops? Are the i's conflicting?
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
4904 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
8 ms |
3588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 6 |
Correct |
0 ms |
316 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2004 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1876 KB |
Output is correct |
| 15 |
Correct |
13 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
14 ms |
4904 KB |
Output is correct |
| 17 |
Correct |
10 ms |
4744 KB |
Output is correct |
| 18 |
Correct |
8 ms |
3660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 2 |
Correct |
57 ms |
28404 KB |
Output is correct |
| 3 |
Correct |
413 ms |
283936 KB |
Output is correct |
| 4 |
Correct |
118 ms |
67184 KB |
Output is correct |
| 5 |
Correct |
255 ms |
160172 KB |
Output is correct |
| 6 |
Correct |
889 ms |
313252 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2180 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2132 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
58 ms |
28316 KB |
Output is correct |
| 14 |
Correct |
32 ms |
16600 KB |
Output is correct |
| 15 |
Correct |
31 ms |
18260 KB |
Output is correct |
| 16 |
Correct |
27 ms |
11996 KB |
Output is correct |
| 17 |
Correct |
154 ms |
72624 KB |
Output is correct |
| 18 |
Correct |
123 ms |
71592 KB |
Output is correct |
| 19 |
Correct |
113 ms |
67080 KB |
Output is correct |
| 20 |
Correct |
96 ms |
61720 KB |
Output is correct |
| 21 |
Correct |
289 ms |
165648 KB |
Output is correct |
| 22 |
Correct |
259 ms |
160172 KB |
Output is correct |
| 23 |
Correct |
383 ms |
137912 KB |
Output is correct |
| 24 |
Correct |
239 ms |
161812 KB |
Output is correct |
| 25 |
Correct |
660 ms |
283988 KB |
Output is correct |
| 26 |
Correct |
707 ms |
317876 KB |
Output is correct |
| 27 |
Correct |
816 ms |
342612 KB |
Output is correct |
| 28 |
Correct |
996 ms |
313248 KB |
Output is correct |
| 29 |
Correct |
1008 ms |
305164 KB |
Output is correct |
| 30 |
Correct |
1008 ms |
317772 KB |
Output is correct |
| 31 |
Correct |
761 ms |
183152 KB |
Output is correct |
| 32 |
Correct |
737 ms |
323100 KB |
Output is correct |
