#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4001;
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int R, C;
char grid[maxn][maxn];
inline bool in(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C;
}
int numcc;
int ccid[maxn][maxn];
vector<vector<int>> adj;
void dfs(int r, int c) {
char was = grid[r][c];
grid[r][c] = '.';
ccid[r][c] = numcc;
for (int d = 0; d < 4; ++d) {
int r1 = r + dr[d], c1 = c + dc[d];
if (in(r1, c1) && grid[r1][c1] == was) {
dfs(r1, c1);
}
}
}
int maxd;
bitset<maxn*maxn> visited;
void dfs2(int u, int d) {
maxd = max(maxd, d);
visited[u] = true;
for (int v : adj[u]) {
if (visited[v] == false) {
dfs2(v, d+1);
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> R >> C;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
cin >> grid[r][c];
}
}
numcc = 0;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (grid[r][c] != '.') {
dfs(r, c);
++numcc;
}
}
}
adj.resize(numcc);
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
for (int d = 0; d < 4; ++d) {
int r1 = r + dr[d], c1= c + dc[d];
if (in(r1, c1) && ccid[r1][c1] != ccid[r][c]) {
adj[ccid[r][c]].push_back(ccid[r1][c1]);
adj[ccid[r1][c1]].push_back(ccid[r][c]);
}
}
}
}
maxd = 0;
dfs2(0, 0);
cout << maxd+1 << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
12148 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
764 KB |
Output isn't correct |
| 4 |
Incorrect |
18 ms |
6900 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
4168 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
532 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1276 KB |
Output isn't correct |
| 10 |
Incorrect |
12 ms |
3700 KB |
Output isn't correct |
| 11 |
Incorrect |
7 ms |
2872 KB |
Output isn't correct |
| 12 |
Incorrect |
22 ms |
5496 KB |
Output isn't correct |
| 13 |
Incorrect |
13 ms |
4212 KB |
Output isn't correct |
| 14 |
Incorrect |
13 ms |
4212 KB |
Output isn't correct |
| 15 |
Incorrect |
49 ms |
11504 KB |
Output isn't correct |
| 16 |
Incorrect |
56 ms |
12040 KB |
Output isn't correct |
| 17 |
Incorrect |
43 ms |
10524 KB |
Output isn't correct |
| 18 |
Incorrect |
19 ms |
6900 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
31736 KB |
Output is correct |
| 2 |
Incorrect |
217 ms |
44616 KB |
Output isn't correct |
| 3 |
Incorrect |
1691 ms |
296800 KB |
Output isn't correct |
| 4 |
Incorrect |
337 ms |
68692 KB |
Output isn't correct |
| 5 |
Execution timed out |
2092 ms |
651268 KB |
Time limit exceeded |
| 6 |
Incorrect |
1779 ms |
252816 KB |
Output isn't correct |
| 7 |
Correct |
31 ms |
33144 KB |
Output is correct |
| 8 |
Correct |
30 ms |
31736 KB |
Output is correct |
| 9 |
Incorrect |
9 ms |
1908 KB |
Output isn't correct |
| 10 |
Correct |
5 ms |
1144 KB |
Output is correct |
| 11 |
Incorrect |
31 ms |
32120 KB |
Output isn't correct |
| 12 |
Incorrect |
8 ms |
3188 KB |
Output isn't correct |
| 13 |
Incorrect |
230 ms |
44636 KB |
Output isn't correct |
| 14 |
Incorrect |
129 ms |
27136 KB |
Output isn't correct |
| 15 |
Incorrect |
156 ms |
37588 KB |
Output isn't correct |
| 16 |
Incorrect |
104 ms |
19400 KB |
Output isn't correct |
| 17 |
Incorrect |
571 ms |
102340 KB |
Output isn't correct |
| 18 |
Incorrect |
645 ms |
130824 KB |
Output isn't correct |
| 19 |
Incorrect |
341 ms |
68692 KB |
Output isn't correct |
| 20 |
Incorrect |
358 ms |
76248 KB |
Output isn't correct |
| 21 |
Incorrect |
955 ms |
185152 KB |
Output isn't correct |
| 22 |
Execution timed out |
2109 ms |
651952 KB |
Time limit exceeded |
| 23 |
Incorrect |
1102 ms |
186468 KB |
Output isn't correct |
| 24 |
Correct |
1361 ms |
309676 KB |
Output is correct |
| 25 |
Execution timed out |
2100 ms |
429532 KB |
Time limit exceeded |
| 26 |
Correct |
1653 ms |
656264 KB |
Output is correct |
| 27 |
Correct |
1381 ms |
412392 KB |
Output is correct |
| 28 |
Incorrect |
1699 ms |
252824 KB |
Output isn't correct |
| 29 |
Incorrect |
1601 ms |
239532 KB |
Output isn't correct |
| 30 |
Incorrect |
1718 ms |
272524 KB |
Output isn't correct |
| 31 |
Execution timed out |
2069 ms |
345632 KB |
Time limit exceeded |
| 32 |
Incorrect |
1631 ms |
401268 KB |
Output isn't correct |
