#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
int n, m, component[4000][4000], ans = 1;
char snow[4000][4000];
int num = 1;
vector<int> graph[16000050];
int visited[16000050];
void floodfill(int c, int x, int y) {
component[x][y] = c;
if (x > 0 && snow[x - 1][y] != '.') {
if (snow[x - 1][y] == snow[x][y] && !component[x - 1][y]) floodfill(c, x - 1, y);
else if (component[x - 1][y]) {
graph[c].push_back(component[x - 1][y]);
graph[component[x - 1][y]].push_back(c);
}
}
if (x < n - 1 && snow[x + 1][y] != '.') {
if (snow[x + 1][y] == snow[x][y] && !component[x + 1][y]) floodfill(c, x + 1, y);
else if (component[x + 1][y]) {
graph[c].push_back(component[x + 1][y]);
graph[component[x + 1][y]].push_back(c);
}
}
if (y > 0 && snow[x][y - 1] != '.') {
if (snow[x][y - 1] == snow[x][y] && !component[x][y - 1]) floodfill(c, x, y - 1);
else if (component[x][y - 1]) {
graph[c].push_back(component[x][y - 1]);
graph[component[x][y - 1]].push_back(c);
}
}
if (y < m - 1 && snow[x][y + 1] != '.') {
if (snow[x][y + 1] == snow[x][y] && !component[x][y + 1]) floodfill(c, x, y + 1);
else if (component[x][y + 1]) {
graph[c].push_back(component[x][y+ 1]);
graph[component[x][y + 1]].push_back(c);
}
}
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
FOR(i, 0, n) FOR(j, 0, m) cin >> snow[i][j];
FOR(i, 0, n) FOR(j, 0, m) {
if (!component[i][j] && snow[i][j] != '.') {
floodfill(num++, i, j);
}
}
queue<int> q;
q.push(1);
visited[1] = 1;
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int i : graph[curr]) {
if (!visited[i]) {
visited[i] = visited[curr] + 1;
ans = max(ans, visited[i]);
q.push(i);
}
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
399 ms |
387272 KB |
Output is correct |
2 |
Correct |
349 ms |
376208 KB |
Output is correct |
3 |
Correct |
351 ms |
376532 KB |
Output is correct |
4 |
Correct |
374 ms |
385392 KB |
Output is correct |
5 |
Correct |
358 ms |
379192 KB |
Output is correct |
6 |
Correct |
349 ms |
376292 KB |
Output is correct |
7 |
Correct |
354 ms |
376572 KB |
Output is correct |
8 |
Correct |
351 ms |
376724 KB |
Output is correct |
9 |
Correct |
350 ms |
376920 KB |
Output is correct |
10 |
Correct |
362 ms |
378936 KB |
Output is correct |
11 |
Correct |
363 ms |
379208 KB |
Output is correct |
12 |
Correct |
368 ms |
380904 KB |
Output is correct |
13 |
Correct |
358 ms |
379252 KB |
Output is correct |
14 |
Correct |
359 ms |
379216 KB |
Output is correct |
15 |
Correct |
397 ms |
385608 KB |
Output is correct |
16 |
Correct |
399 ms |
387132 KB |
Output is correct |
17 |
Correct |
381 ms |
383532 KB |
Output is correct |
18 |
Correct |
373 ms |
385356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
385 ms |
407156 KB |
Output is correct |
2 |
Correct |
518 ms |
406336 KB |
Output is correct |
3 |
Correct |
1312 ms |
530800 KB |
Output is correct |
4 |
Correct |
568 ms |
421060 KB |
Output is correct |
5 |
Correct |
1282 ms |
587568 KB |
Output is correct |
6 |
Execution timed out |
2079 ms |
841336 KB |
Time limit exceeded |
7 |
Correct |
387 ms |
408840 KB |
Output is correct |
8 |
Correct |
386 ms |
407276 KB |
Output is correct |
9 |
Correct |
359 ms |
377300 KB |
Output is correct |
10 |
Correct |
353 ms |
376592 KB |
Output is correct |
11 |
Correct |
382 ms |
407656 KB |
Output is correct |
12 |
Correct |
358 ms |
377848 KB |
Output is correct |
13 |
Correct |
509 ms |
406292 KB |
Output is correct |
14 |
Correct |
446 ms |
395316 KB |
Output is correct |
15 |
Correct |
435 ms |
394940 KB |
Output is correct |
16 |
Correct |
428 ms |
390064 KB |
Output is correct |
17 |
Correct |
754 ms |
443500 KB |
Output is correct |
18 |
Correct |
672 ms |
434672 KB |
Output is correct |
19 |
Correct |
570 ms |
421136 KB |
Output is correct |
20 |
Correct |
570 ms |
421548 KB |
Output is correct |
21 |
Correct |
929 ms |
480140 KB |
Output is correct |
22 |
Correct |
1293 ms |
587632 KB |
Output is correct |
23 |
Correct |
1123 ms |
496044 KB |
Output is correct |
24 |
Correct |
965 ms |
487824 KB |
Output is correct |
25 |
Correct |
1894 ms |
564728 KB |
Output is correct |
26 |
Runtime error |
1376 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
27 |
Execution timed out |
2144 ms |
1028756 KB |
Time limit exceeded |
28 |
Execution timed out |
2098 ms |
849500 KB |
Time limit exceeded |
29 |
Execution timed out |
2152 ms |
849452 KB |
Time limit exceeded |
30 |
Execution timed out |
2138 ms |
884864 KB |
Time limit exceeded |
31 |
Execution timed out |
2105 ms |
710296 KB |
Time limit exceeded |
32 |
Execution timed out |
2141 ms |
939128 KB |
Time limit exceeded |