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>
#include <iostream>
#define c(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)
#define ll long long
#define f first
#define s second
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mp make_pair
using namespace std;
vector<string> F;
vector<vector<int>> G;
vector<set<int>> A;
int N, M;
bool ok(int I, int J){
if(I < 0 || I >= N || J < 0 || J >= M) return false;
return true;
}
void dfs(int I, int J, char a, int e){
if(!ok(I, J)) return;
if(F[I][J] != a || G[I][J]) return;
G[I][J] = e;
if(ok(I+1, J)){
int b = G[I+1][J];
if(b != 0 && b != e){
A[b].insert(e);
A[e].insert(b);
}
}
if(ok(I, J+1)){
int b = G[I][J+1];
if(b != 0 && b != e){
A[b].insert(e);
A[e].insert(b);
}
}
if(ok(I-1, J)){
int b = G[I-1][J];
if(b != 0 && b != e){
A[b].insert(e);
A[e].insert(b);
}
}
if(ok(I, J-1)){
int b = G[I][J-1];
if(b != 0 && b != e){
A[b].insert(e);
A[e].insert(b);
}
}
dfs(I+1, J, a, e);
dfs(I, J+1, a, e);
dfs(I-1, J, a, e);
dfs(I, J-1, a, e);
}
int bfs(){
int D = A.size();
vector<bool> V(D);
queue<pair<int, int>> q;
q.push({1, 1});
int ris = 0;
while(!q.empty()){
int n = q.front().f, d = q.front().s;
q.pop();
if(V[n]) continue;
V[n] = true;
ris = max(ris, d);
for(int v: A[n]){
q.push({v, d+1});
}
}
return ris;
}
int main(){
ifstream in("input.txt");
ofstream out("output.txt");
cin >> N >> M;
F.resize(N);
for(int i=0; i<N; i++){
cin >> F[i];
}
G.resize(N, vector<int>(M, 0));
A.pb(set<int>());
int e = 1;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(!G[i][j] && F[i][j] != '.'){
A.pb(set<int>());
dfs(i, j, F[0][j], e);
e++;
}
}
}
cout << bfs();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |