#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=4000;
char a[mx][mx];
bool vis[mx][mx];
int dist[mx][mx];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
memset(vis, 0, sizeof(vis));
memset(dist, 0x3f, sizeof(dist));
cin>>n>>m;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];
deque<pair<int, int>> q;
q.push_front({0, 0});
dist[0][0]=1;
int mxd=0;
while(!q.empty()){
auto [x, y] = q.front();
q.pop_front();
if(vis[x][y])continue;
vis[x][y]=1;
mxd=max(mxd, dist[x][y]);
for(int i=0;i<4;i++){
int nx = x+dx[i], ny=y+dy[i];
if(nx<0||ny<0||nx>=n||ny>=m)continue;
if(vis[nx][ny])continue;
if(a[nx][ny]=='.')continue;
if(a[nx][ny]!=a[x][y])q.push_back({nx, ny}), dist[nx][ny]=dist[x][y]+1;
else q.push_front({nx, ny}), dist[nx][ny]=dist[x][y];
}
}
cout<<mxd;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
80988 KB |
Output is correct |
| 2 |
Correct |
13 ms |
80580 KB |
Output is correct |
| 3 |
Correct |
13 ms |
80472 KB |
Output is correct |
| 4 |
Correct |
19 ms |
80976 KB |
Output is correct |
| 5 |
Correct |
14 ms |
80732 KB |
Output is correct |
| 6 |
Correct |
12 ms |
80696 KB |
Output is correct |
| 7 |
Correct |
12 ms |
80472 KB |
Output is correct |
| 8 |
Correct |
13 ms |
80472 KB |
Output is correct |
| 9 |
Correct |
14 ms |
80600 KB |
Output is correct |
| 10 |
Correct |
16 ms |
80732 KB |
Output is correct |
| 11 |
Correct |
15 ms |
80724 KB |
Output is correct |
| 12 |
Correct |
17 ms |
80732 KB |
Output is correct |
| 13 |
Correct |
18 ms |
80708 KB |
Output is correct |
| 14 |
Correct |
18 ms |
80732 KB |
Output is correct |
| 15 |
Correct |
22 ms |
82964 KB |
Output is correct |
| 16 |
Correct |
24 ms |
80932 KB |
Output is correct |
| 17 |
Correct |
18 ms |
80904 KB |
Output is correct |
| 18 |
Correct |
17 ms |
81052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
93736 KB |
Output is correct |
| 2 |
Correct |
52 ms |
86312 KB |
Output is correct |
| 3 |
Correct |
274 ms |
110020 KB |
Output is correct |
| 4 |
Correct |
77 ms |
89772 KB |
Output is correct |
| 5 |
Correct |
185 ms |
99260 KB |
Output is correct |
| 6 |
Correct |
748 ms |
134328 KB |
Output is correct |
| 7 |
Correct |
15 ms |
94300 KB |
Output is correct |
| 8 |
Correct |
15 ms |
93668 KB |
Output is correct |
| 9 |
Correct |
11 ms |
80728 KB |
Output is correct |
| 10 |
Correct |
10 ms |
80612 KB |
Output is correct |
| 11 |
Correct |
15 ms |
94044 KB |
Output is correct |
| 12 |
Correct |
10 ms |
80472 KB |
Output is correct |
| 13 |
Correct |
51 ms |
85084 KB |
Output is correct |
| 14 |
Correct |
34 ms |
83544 KB |
Output is correct |
| 15 |
Correct |
28 ms |
83548 KB |
Output is correct |
| 16 |
Correct |
30 ms |
81244 KB |
Output is correct |
| 17 |
Correct |
132 ms |
90452 KB |
Output is correct |
| 18 |
Correct |
77 ms |
90460 KB |
Output is correct |
| 19 |
Correct |
72 ms |
89680 KB |
Output is correct |
| 20 |
Correct |
68 ms |
88912 KB |
Output is correct |
| 21 |
Correct |
159 ms |
99924 KB |
Output is correct |
| 22 |
Correct |
148 ms |
99260 KB |
Output is correct |
| 23 |
Correct |
210 ms |
95980 KB |
Output is correct |
| 24 |
Correct |
158 ms |
99800 KB |
Output is correct |
| 25 |
Correct |
355 ms |
110200 KB |
Output is correct |
| 26 |
Correct |
645 ms |
204364 KB |
Output is correct |
| 27 |
Correct |
692 ms |
160336 KB |
Output is correct |
| 28 |
Correct |
761 ms |
134464 KB |
Output is correct |
| 29 |
Correct |
780 ms |
131644 KB |
Output is correct |
| 30 |
Correct |
732 ms |
144952 KB |
Output is correct |
| 31 |
Correct |
530 ms |
102108 KB |
Output is correct |
| 32 |
Correct |
678 ms |
160076 KB |
Output is correct |
