//JAI BAJRANG BALI
#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
using namespace std;
// #ifndef ONLINE_JUDGE
// #include "./debugging.hpp" // pathname
// #else
// #define debug(...)
// #endif
#define ndl "\n"
typedef long long int ll;
typedef unsigned long long int ull;
//#define int long long
// ... Rest of your template code ...
#define out1(x) cout<<x<<"\n";
#define out(x) cout<<x<<" ";
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(), greater<ll>())
#define yes() std::cout << "YES\n";
#define no() std::cout << "NO\n";
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define p 998244353
using ll = long long;
vll dx={1,-1,0,0};
vll dy={0,0,-1,1};
// 1,0 -1,0 0,-1 0,1
void solve(ll tc){
ll n,m; cin>>n>>m; vector<string> steps(n);
vector<vll> d(n,vll(m,0));
for(ll i=0;i<n;i++){
cin>>steps[i];
}
d[0][0]=1;
ll ans=1;
deque<vll> q;
q.push_front({0,0});
while(!q.empty()){
vll v1=q.front(); q.pop_front();
ll x1=v1[0]; ll y1=v1[1];
ans=max(ans,d[x1][y1]);
for(ll i=0;i<4;i++){
ll new_x=x1+dx[i];
ll new_y=y1+dy[i];
if(new_x>=0 and new_y>=0 and new_x<n and new_y<n and (steps[new_x][new_y]!='.')){
ll weight=0;
if(steps[new_x][new_y]!=steps[x1][y1]) {
weight++;
}
if(d[new_x][new_y]==0){
d[new_x][new_y]=d[x1][y1]+weight;
if(weight==0){
q.push_front({new_x,new_y});
}
else{
q.push_back({new_x,new_y});
}
}
}
}
}
out1(ans);
}
signed main(){
ll T=1;
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cin>>T;
for (ll tc = 1; tc <=T; tc++) solve(tc);
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Integer overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
3224 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
456 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3164 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1372 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1312 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 15 |
Correct |
15 ms |
2904 KB |
Output is correct |
| 16 |
Incorrect |
24 ms |
3264 KB |
Output isn't correct |
| 17 |
Correct |
10 ms |
2908 KB |
Output is correct |
| 18 |
Correct |
11 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
55 ms |
15868 KB |
Output is correct |
| 3 |
Correct |
306 ms |
159304 KB |
Output is correct |
| 4 |
Incorrect |
69 ms |
37460 KB |
Output isn't correct |
| 5 |
Correct |
211 ms |
89424 KB |
Output is correct |
| 6 |
Correct |
1387 ms |
250988 KB |
Output is correct |
| 7 |
Correct |
2 ms |
860 KB |
Output is correct |
| 8 |
Correct |
2 ms |
976 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 11 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
57 ms |
15964 KB |
Output is correct |
| 14 |
Incorrect |
32 ms |
9308 KB |
Output isn't correct |
| 15 |
Correct |
25 ms |
10328 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
6748 KB |
Output isn't correct |
| 17 |
Correct |
143 ms |
40708 KB |
Output is correct |
| 18 |
Correct |
91 ms |
39812 KB |
Output is correct |
| 19 |
Incorrect |
75 ms |
37560 KB |
Output isn't correct |
| 20 |
Incorrect |
16 ms |
34360 KB |
Output isn't correct |
| 21 |
Correct |
176 ms |
92512 KB |
Output is correct |
| 22 |
Correct |
212 ms |
89432 KB |
Output is correct |
| 23 |
Incorrect |
231 ms |
77412 KB |
Output isn't correct |
| 24 |
Correct |
175 ms |
90640 KB |
Output is correct |
| 25 |
Correct |
582 ms |
159264 KB |
Output is correct |
| 26 |
Correct |
938 ms |
463816 KB |
Output is correct |
| 27 |
Correct |
1133 ms |
306748 KB |
Output is correct |
| 28 |
Correct |
1375 ms |
251428 KB |
Output is correct |
| 29 |
Correct |
1409 ms |
238260 KB |
Output is correct |
| 30 |
Correct |
1307 ms |
267268 KB |
Output is correct |
| 31 |
Incorrect |
973 ms |
105216 KB |
Output isn't correct |
| 32 |
Correct |
978 ms |
246408 KB |
Output is correct |
