#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int depth[4000][4000];
int main() {_
int n,m;
cin>>n>>m;
char num[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>num[i][j];
}
}
deque<pair<int,int>> dq;
dq.push_back({0,0});
depth[0][0]=1;
int ans=0;
while(!dq.empty()){
pair<int,int> temp=dq.front();
int x=temp.f;
int y=temp.s;
dq.pop_front();
ans=max(ans,depth[x][y]);
for(int i=0;i<4;i++){
if(0<=x+dx[i] && x+dx[i]<n && 0<=y+dy[i] && y+dy[i]<m && num[x+dx[i]][y+dy[i]]!='.' && depth[x+dx[i]][y+dy[i]]==0){
if(num[x+dx[i]][y+dy[i]]==num[x][y]){
depth[x+dx[i]][y+dy[i]]=depth[x][y];
dq.push_front({x+dx[i],y+dy[i]});
}
else{
depth[x+dx[i]][y+dy[i]]=depth[x][y]+1;
dq.push_back({x+dx[i],y+dy[i]});
}
}
}
}
cout<<ans;
return 0;
}
//maybe its multiset not set
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
3796 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
9 ms |
3412 KB |
Output is correct |
5 |
Correct |
4 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
456 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
3 ms |
1492 KB |
Output is correct |
11 |
Correct |
2 ms |
1364 KB |
Output is correct |
12 |
Correct |
5 ms |
2004 KB |
Output is correct |
13 |
Correct |
3 ms |
1876 KB |
Output is correct |
14 |
Correct |
3 ms |
1884 KB |
Output is correct |
15 |
Correct |
12 ms |
3540 KB |
Output is correct |
16 |
Correct |
13 ms |
3776 KB |
Output is correct |
17 |
Correct |
11 ms |
3540 KB |
Output is correct |
18 |
Correct |
8 ms |
3328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16016 KB |
Output is correct |
2 |
Correct |
49 ms |
11688 KB |
Output is correct |
3 |
Correct |
357 ms |
73308 KB |
Output is correct |
4 |
Correct |
100 ms |
29004 KB |
Output is correct |
5 |
Correct |
249 ms |
50324 KB |
Output is correct |
6 |
Correct |
699 ms |
107896 KB |
Output is correct |
7 |
Correct |
12 ms |
16980 KB |
Output is correct |
8 |
Correct |
10 ms |
16084 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
10 ms |
16296 KB |
Output is correct |
12 |
Correct |
2 ms |
980 KB |
Output is correct |
13 |
Correct |
58 ms |
11696 KB |
Output is correct |
14 |
Correct |
30 ms |
7756 KB |
Output is correct |
15 |
Correct |
29 ms |
10112 KB |
Output is correct |
16 |
Correct |
24 ms |
4776 KB |
Output is correct |
17 |
Correct |
134 ms |
24876 KB |
Output is correct |
18 |
Correct |
102 ms |
31900 KB |
Output is correct |
19 |
Correct |
99 ms |
28924 KB |
Output is correct |
20 |
Correct |
91 ms |
21980 KB |
Output is correct |
21 |
Correct |
210 ms |
49644 KB |
Output is correct |
22 |
Correct |
253 ms |
50296 KB |
Output is correct |
23 |
Correct |
238 ms |
41556 KB |
Output is correct |
24 |
Correct |
232 ms |
46288 KB |
Output is correct |
25 |
Correct |
529 ms |
94228 KB |
Output is correct |
26 |
Correct |
479 ms |
129328 KB |
Output is correct |
27 |
Correct |
613 ms |
120744 KB |
Output is correct |
28 |
Correct |
726 ms |
107744 KB |
Output is correct |
29 |
Correct |
705 ms |
106328 KB |
Output is correct |
30 |
Correct |
651 ms |
110164 KB |
Output is correct |
31 |
Correct |
567 ms |
70804 KB |
Output is correct |
32 |
Correct |
528 ms |
106332 KB |
Output is correct |