This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vpl = vector<pl>;
using vpi = vector<pi>;
using vc = vector<char>;
using vs = vector<string>;
#define forn(i, n) for(int i = 0; i < n; i++)
#define rofn(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, b, a) for(int i = b; i >= a; i--)
#define TRAV(a, x) for(auto& a: x)
#define ABC(c) for(char c = 'a'; c <= 'z'; c++)
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(all(x), greater<int>())
#define pb push_back
#define mp make_pair
#define ins insert
#define ub upper_bound
#define lb lower_bound
#define len(x) (int)(x).length()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) TRAV(a, x) cout << a << " "
#define print(x) cout << x << endl
#define traverse(x) TRAV(a, x) cout << a.f << " " << a.s << endl
#define readvi(a, n) forn(i, n) cin >> a[i]
#define readvpi(a, n) forn(i, n) cin >> a[i].f >> a[i].s
#define gcd(a, b) __gcd(a, b)
const int MAXN = 4000, INF = 1e9;
char grid[MAXN][MAXN]; int vis[MAXN][MAXN], comp[MAXN][MAXN], h, w, cur;
int xDir[4] = {1, -1, 0, 0}, yDir[4] = {0, 0, 1, -1};
bool vis1[MAXN * MAXN + 1];
void floodfill(int i, int j, char animal){
if(i >= h || j >= w || i < 0 || j < 0 || grid[i][j] != animal || vis[i][j]){
return;
}
vis[i][j] = true;
comp[i][j] = cur;
forn(k, 4){
floodfill(i + xDir[k], j + yDir[k], animal);
}
}
void solve(){
cin >> h >> w;
forn(i, h){
forn(j, w){
cin >> grid[i][j];
}
}
cur = 1;
forn(i, h){
forn(j, w){
if(grid[i][j] != '.' && !vis[i][j]){
floodfill(i, j, grid[i][j]);
++cur;
}
}
}
vi adj[cur + 1], dist(cur + 1, INF);
forn(i, h){
forn(j, w){
if(comp[i][j]){
forn(k, 4){
int x = i + xDir[k], y = j + yDir[k];
if(x && y && comp[x][y] && (comp[x][y] != comp[i][j])){
adj[comp[i][j]].pb(comp[x][y]);
adj[comp[x][y]].pb(comp[i][j]);
}
}
}
}
}
queue<int> q;
q.push(comp[0][0]);
dist[comp[0][0]] = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
if(vis1[cur]){
continue;
}
vis1[cur] = true;
TRAV(a, adj[cur]){
if(dist[a] > dist[cur] + 1){
dist[a] = dist[cur] + 1;
}
q.push(a);
}
}
int ans = 0;
FOR(i, 1, cur){
ans = max(ans, dist[i]);
}
cout << ++ans << endl;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
// int t; cin >> t;
// forn(i, t){
// solve();
// }
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |