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>
#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 4005; /// mind this
const int MAX = 2e6 + 123;
const int BS = 61;
const int mod = 998244353;
bool used[sz][sz];
char c[sz][sz];
deque<array<ll, 3>> bfs;
vector<array<ll, 2>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void solve(){
ll n, m, i, j, cnt = 0, ans = 0;
cin >> n >> m;
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
cin >> c[i][j];
if(c[i][j] != '.'){
cnt ++;
}
}
}
bfs.push_back({1, 1, 1});
while(cnt){
array<ll, 3> cur = bfs.back();
bfs.pop_back();
ans = max(ans, cur[2]);
if(used[cur[0]][cur[1]]){continue;}
used[cur[0]][cur[1]] = 1;
if(!(--cnt)){break;}
for(array<ll, 2> d: dir){
ll nx = cur[0] + d[0], ny = cur[1] + d[1];
if(!used[nx][ny]){
if(c[nx][ny] == c[cur[0]][cur[1]]){
bfs.pb({nx, ny, cur[2]});
}
else{
bfs.push_front({nx, ny, cur[2] + 1});
}
}
}
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
// cin >> t;
while(t--){
solve();
}
}
/*
123 321
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |