#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ref(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define rep(a,b) for(int (a)=0;(a)<(b);++(a))
#define pb push_back
#define mp make_pair
const int mx=5000;
int n,m;
char a[mx][mx];
int depth[mx][mx];
int vis[mx][mx];
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
int check(int x,int y){
if(x==0 or y==0 or x==n+1 or y==m+1 or a[x][y]=='.' or vis[x][y])return 1;
else return 0;
}
int ans=1;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin >> a[i][j];
}
}
rep(i,mx)rep(j,mx)depth[i][j]=2e9;
depth[1][1]=1;
deque <pair <int,int> > q;
q.push_front(mp(1,1));
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop_front();
if(vis[x][y])continue;
else vis[x][y]=1;
//cout << x << " " << y << " " << depth[x][y] << endl;
//if(x==1 and y==5)cout<<"BURda";
ans=max(ans,depth[x][y]);
for(int i=0;i<4;++i){
int gox=x+dx[i];int goy=y+dy[i];
// if(x==1 and y==5)cout<<gox << " " << goy << endl;
if(check(gox,goy))continue;
if(a[gox][goy]==a[x][y] and depth[gox][goy]>depth[x][y]){
depth[gox][goy]=depth[x][y];
q.push_front(mp(gox,goy));
// if(x==1 and y==5)cout<<"BURDa 1 " << i << endl;
}
else if(a[gox][goy]!=a[x][y] and depth[gox][goy]>depth[x][y]+1){
depth[gox][goy]=depth[x][y]+1;
q.push_back(mp(gox,goy));
//if(x==1 and y==5)cout<<"BURDa 2 " << i << endl;
}
}
}
cout << ans << endl;
}
Compilation message
tracks.cpp: In function 'int main()':
tracks.cpp:5:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define rep(a,b) for(int (a)=0;(a)<(b);++(a))
| ^
tracks.cpp:28:2: note: in expansion of macro 'rep'
28 | rep(i,mx)rep(j,mx)depth[i][j]=2e9;
| ^~~
tracks.cpp:5:26: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
5 | #define rep(a,b) for(int (a)=0;(a)<(b);++(a))
| ^
tracks.cpp:28:11: note: in expansion of macro 'rep'
28 | rep(i,mx)rep(j,mx)depth[i][j]=2e9;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
103404 KB |
Output is correct |
| 2 |
Correct |
58 ms |
98412 KB |
Output is correct |
| 3 |
Correct |
60 ms |
98540 KB |
Output is correct |
| 4 |
Correct |
70 ms |
103148 KB |
Output is correct |
| 5 |
Correct |
61 ms |
100844 KB |
Output is correct |
| 6 |
Correct |
58 ms |
98412 KB |
Output is correct |
| 7 |
Correct |
58 ms |
98540 KB |
Output is correct |
| 8 |
Correct |
58 ms |
98668 KB |
Output is correct |
| 9 |
Correct |
66 ms |
99052 KB |
Output is correct |
| 10 |
Correct |
64 ms |
100400 KB |
Output is correct |
| 11 |
Correct |
62 ms |
100076 KB |
Output is correct |
| 12 |
Correct |
70 ms |
101248 KB |
Output is correct |
| 13 |
Correct |
63 ms |
100972 KB |
Output is correct |
| 14 |
Correct |
62 ms |
100844 KB |
Output is correct |
| 15 |
Correct |
79 ms |
103276 KB |
Output is correct |
| 16 |
Correct |
94 ms |
103404 KB |
Output is correct |
| 17 |
Correct |
77 ms |
103148 KB |
Output is correct |
| 18 |
Correct |
73 ms |
103148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
129004 KB |
Output is correct |
| 2 |
Correct |
137 ms |
112620 KB |
Output is correct |
| 3 |
Correct |
513 ms |
162224 KB |
Output is correct |
| 4 |
Correct |
200 ms |
129004 KB |
Output is correct |
| 5 |
Correct |
354 ms |
145516 KB |
Output is correct |
| 6 |
Correct |
1242 ms |
210260 KB |
Output is correct |
| 7 |
Correct |
78 ms |
130540 KB |
Output is correct |
| 8 |
Correct |
76 ms |
129132 KB |
Output is correct |
| 9 |
Correct |
61 ms |
98540 KB |
Output is correct |
| 10 |
Correct |
59 ms |
98284 KB |
Output is correct |
| 11 |
Correct |
76 ms |
129900 KB |
Output is correct |
| 12 |
Correct |
60 ms |
99564 KB |
Output is correct |
| 13 |
Correct |
139 ms |
112620 KB |
Output is correct |
| 14 |
Correct |
104 ms |
108268 KB |
Output is correct |
| 15 |
Correct |
101 ms |
110956 KB |
Output is correct |
| 16 |
Correct |
95 ms |
103532 KB |
Output is correct |
| 17 |
Correct |
264 ms |
124780 KB |
Output is correct |
| 18 |
Correct |
224 ms |
131712 KB |
Output is correct |
| 19 |
Correct |
197 ms |
128876 KB |
Output is correct |
| 20 |
Correct |
167 ms |
121836 KB |
Output is correct |
| 21 |
Correct |
326 ms |
144492 KB |
Output is correct |
| 22 |
Correct |
343 ms |
145516 KB |
Output is correct |
| 23 |
Correct |
450 ms |
136300 KB |
Output is correct |
| 24 |
Correct |
316 ms |
141804 KB |
Output is correct |
| 25 |
Correct |
813 ms |
196076 KB |
Output is correct |
| 26 |
Correct |
741 ms |
227452 KB |
Output is correct |
| 27 |
Correct |
1004 ms |
209532 KB |
Output is correct |
| 28 |
Correct |
1230 ms |
210428 KB |
Output is correct |
| 29 |
Correct |
1233 ms |
208764 KB |
Output is correct |
| 30 |
Correct |
1100 ms |
209784 KB |
Output is correct |
| 31 |
Correct |
1136 ms |
167404 KB |
Output is correct |
| 32 |
Correct |
874 ms |
209888 KB |
Output is correct |
