#include <bits/stdc++.h>
using namespace std;
const int mxN = 4000;
int H, W, id[mxN][mxN];
char grid[mxN][mxN];
bool vis[mxN][mxN];
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
vector<int> dist;
queue<pair<int, int>> q;
void ff(int r, int c, int x) {
id[r][c] = x;
for (int i=0; i<4; ++i) {
int nr = r + dx[i], nc = c + dy[i];
if (nr >= 0 && nr < H && nc >= 0 && nc < W &&
grid[nr][nc] == grid[r][c] && !id[nr][nc]) {
ff(nr, nc, x);
}
}
}
void ff2(int r, int c) {
vis[r][c] = true;
for (int i=0; i<4; ++i) {
int nr = r + dx[i], nc = c + dy[i];
if (nr >= 0 && nr < H && nc >= 0 && nc < W &&
!vis[nr][nc] && grid[nr][nc] != '.') {
if (grid[nr][nc] != grid[r][c]) {
if (dist[id[nr][nc]] == 2e9) {
dist[id[nr][nc]] = dist[id[r][c]] + 1;
q.push({nr, nc});
}
} else {
ff2(nr, nc);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> H >> W;
for (int i=0; i<H; ++i)
for (int j=0; j<W; ++j)
cin >> grid[i][j];
int cur = 0;
for (int i=0; i<H; ++i) {
for (int j=0; j<W; ++j) {
if (!id[i][j] && grid[i][j] != '.')
ff(i, j, ++cur);
}
}
dist.resize(cur+1, 2e9);
queue<pair<int, int>> q;
q.push({0, 0});
dist[1] = 0;
while (!q.empty()) {
int r = q.front().first;
int c = q.front().second;
q.pop();
ff2(r, c);
}
int ans = 0;
for (int i=1; i<=cur; ++i)
ans = max(ans, dist[i]);
cout << ans + 1 << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
7552 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 4 |
Incorrect |
10 ms |
8096 KB |
Output isn't correct |
| 5 |
Incorrect |
5 ms |
4180 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
1560 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
3540 KB |
Output isn't correct |
| 11 |
Incorrect |
3 ms |
3284 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
4308 KB |
Output isn't correct |
| 13 |
Incorrect |
4 ms |
4180 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
4096 KB |
Output isn't correct |
| 15 |
Incorrect |
12 ms |
7480 KB |
Output isn't correct |
| 16 |
Incorrect |
14 ms |
7636 KB |
Output isn't correct |
| 17 |
Incorrect |
9 ms |
7296 KB |
Output isn't correct |
| 18 |
Incorrect |
9 ms |
8152 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
46320 KB |
Output isn't correct |
| 2 |
Incorrect |
42 ms |
21000 KB |
Output isn't correct |
| 3 |
Incorrect |
283 ms |
84332 KB |
Output isn't correct |
| 4 |
Incorrect |
72 ms |
41480 KB |
Output isn't correct |
| 5 |
Incorrect |
164 ms |
78632 KB |
Output isn't correct |
| 6 |
Incorrect |
657 ms |
140904 KB |
Output isn't correct |
| 7 |
Incorrect |
23 ms |
48596 KB |
Output isn't correct |
| 8 |
Incorrect |
23 ms |
46300 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
848 KB |
Output isn't correct |
| 11 |
Incorrect |
22 ms |
47376 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
2260 KB |
Output isn't correct |
| 13 |
Incorrect |
42 ms |
20980 KB |
Output isn't correct |
| 14 |
Incorrect |
25 ms |
14588 KB |
Output isn't correct |
| 15 |
Incorrect |
25 ms |
17740 KB |
Output isn't correct |
| 16 |
Incorrect |
19 ms |
7872 KB |
Output isn't correct |
| 17 |
Incorrect |
96 ms |
39140 KB |
Output isn't correct |
| 18 |
Incorrect |
84 ms |
46224 KB |
Output isn't correct |
| 19 |
Incorrect |
73 ms |
41488 KB |
Output isn't correct |
| 20 |
Incorrect |
68 ms |
34168 KB |
Output isn't correct |
| 21 |
Incorrect |
163 ms |
63552 KB |
Output isn't correct |
| 22 |
Incorrect |
180 ms |
78356 KB |
Output isn't correct |
| 23 |
Incorrect |
187 ms |
54092 KB |
Output isn't correct |
| 24 |
Incorrect |
164 ms |
63172 KB |
Output isn't correct |
| 25 |
Incorrect |
307 ms |
107368 KB |
Output isn't correct |
| 26 |
Runtime error |
1309 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Incorrect |
915 ms |
446520 KB |
Output isn't correct |
| 28 |
Incorrect |
695 ms |
137468 KB |
Output isn't correct |
| 29 |
Incorrect |
668 ms |
142468 KB |
Output isn't correct |
| 30 |
Incorrect |
715 ms |
186728 KB |
Output isn't correct |
| 31 |
Incorrect |
465 ms |
82012 KB |
Output isn't correct |
| 32 |
Incorrect |
740 ms |
368468 KB |
Output isn't correct |
