#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 4005;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int H, W;
char grid[MX][MX];
int dist[MX][MX];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
for(int i = 0; i < MX; i++)
for(int j = 0; j < MX; j++)
dist[i][j] = -1;
cin >> H >> W;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
cin >> grid[i][j];
}
}
deque<pair<int,int>> dq;
dq.push_front({0, 0});
dist[0][0] = 0;
int ans = 0;
while(!dq.empty()) {
auto [x, y] = dq.front(); dq.pop_front();
ans = max(ans, dist[x][y]);
for(int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if(nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] != '.' && dist[nx][ny] == -1) {
if(grid[x][y] == grid[nx][ny]) {
dist[nx][ny] = dist[x][y];
dq.push_front({nx, ny});
} else {
dist[nx][ny] = dist[x][y] + 1;
dq.push_back({nx, ny});
}
}
}
}
cout << ans + 1 << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
65236 KB |
Output is correct |
2 |
Correct |
23 ms |
63112 KB |
Output is correct |
3 |
Correct |
26 ms |
63224 KB |
Output is correct |
4 |
Correct |
29 ms |
65364 KB |
Output is correct |
5 |
Correct |
25 ms |
64308 KB |
Output is correct |
6 |
Correct |
24 ms |
63188 KB |
Output is correct |
7 |
Correct |
23 ms |
63236 KB |
Output is correct |
8 |
Correct |
23 ms |
63316 KB |
Output is correct |
9 |
Correct |
25 ms |
63460 KB |
Output is correct |
10 |
Correct |
26 ms |
64084 KB |
Output is correct |
11 |
Correct |
26 ms |
63956 KB |
Output is correct |
12 |
Correct |
27 ms |
64296 KB |
Output is correct |
13 |
Correct |
26 ms |
64244 KB |
Output is correct |
14 |
Correct |
27 ms |
64212 KB |
Output is correct |
15 |
Correct |
36 ms |
65364 KB |
Output is correct |
16 |
Correct |
34 ms |
65300 KB |
Output is correct |
17 |
Correct |
31 ms |
65164 KB |
Output is correct |
18 |
Correct |
31 ms |
65364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
78048 KB |
Output is correct |
2 |
Correct |
63 ms |
68712 KB |
Output is correct |
3 |
Correct |
278 ms |
80428 KB |
Output is correct |
4 |
Correct |
91 ms |
71124 KB |
Output is correct |
5 |
Correct |
163 ms |
76000 KB |
Output is correct |
6 |
Correct |
657 ms |
93932 KB |
Output is correct |
7 |
Correct |
30 ms |
78732 KB |
Output is correct |
8 |
Correct |
34 ms |
78104 KB |
Output is correct |
9 |
Correct |
25 ms |
63152 KB |
Output is correct |
10 |
Correct |
26 ms |
63028 KB |
Output is correct |
11 |
Correct |
31 ms |
78476 KB |
Output is correct |
12 |
Correct |
25 ms |
63668 KB |
Output is correct |
13 |
Correct |
63 ms |
68368 KB |
Output is correct |
14 |
Correct |
46 ms |
67040 KB |
Output is correct |
15 |
Correct |
47 ms |
67304 KB |
Output is correct |
16 |
Correct |
44 ms |
65032 KB |
Output is correct |
17 |
Correct |
120 ms |
71776 KB |
Output is correct |
18 |
Correct |
104 ms |
71600 KB |
Output is correct |
19 |
Correct |
98 ms |
71252 KB |
Output is correct |
20 |
Correct |
83 ms |
70728 KB |
Output is correct |
21 |
Correct |
170 ms |
76168 KB |
Output is correct |
22 |
Correct |
165 ms |
75600 KB |
Output is correct |
23 |
Correct |
211 ms |
73640 KB |
Output is correct |
24 |
Correct |
167 ms |
75992 KB |
Output is correct |
25 |
Correct |
457 ms |
79836 KB |
Output is correct |
26 |
Correct |
402 ms |
128212 KB |
Output is correct |
27 |
Correct |
549 ms |
114496 KB |
Output is correct |
28 |
Correct |
606 ms |
93796 KB |
Output is correct |
29 |
Correct |
609 ms |
91620 KB |
Output is correct |
30 |
Correct |
567 ms |
99164 KB |
Output is correct |
31 |
Correct |
473 ms |
76060 KB |
Output is correct |
32 |
Correct |
534 ms |
104548 KB |
Output is correct |