#include <iostream>
#include <cassert>
#include <cstring>
#include <queue>
#define ll long long
using namespace std;
const int NMAX = 4000;
const int di[] = { 0, 0, 1, -1 };
const int dj[] = { 1, -1, 0, 0 };
struct Triplet {
int i, j, k;
};
int n, m, answer;
char a[NMAX + 1][NMAX + 1];
char done[NMAX + 1][NMAX + 1];
deque<Triplet> dq;
bool InMat(int i, int j) {
return i >= 1 && i <= n && j >= 1 && j <= m;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
dq.push_back({1, 1, 1});
while (!dq.empty()) {
auto [i, j, k] = dq.back();
dq.pop_back();
if (!done[i][j]) {
done[i][j] = 1;
answer = max(answer, k);
for (int d = 0; d < 4; d++) {
int inou = i + di[d];
int jnou = j + dj[d];
if (InMat(inou, jnou) && a[inou][jnou] != '.') {
if (a[inou][jnou] == a[i][j]) {
dq.push_back({ inou, jnou, k });
}
else {
dq.push_front({ inou, jnou, k + 1 });
}
}
}
}
}
cout << answer << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
4692 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
852 KB |
Output is correct |
| 4 |
Correct |
12 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
852 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2388 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2132 KB |
Output is correct |
| 12 |
Correct |
7 ms |
2828 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2836 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
15 ms |
4692 KB |
Output is correct |
| 16 |
Correct |
20 ms |
4692 KB |
Output is correct |
| 17 |
Correct |
11 ms |
4436 KB |
Output is correct |
| 18 |
Correct |
16 ms |
5004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
30292 KB |
Output is correct |
| 2 |
Correct |
51 ms |
11860 KB |
Output is correct |
| 3 |
Correct |
305 ms |
47436 KB |
Output is correct |
| 4 |
Correct |
99 ms |
18744 KB |
Output is correct |
| 5 |
Correct |
150 ms |
32720 KB |
Output is correct |
| 6 |
Correct |
1087 ms |
97920 KB |
Output is correct |
| 7 |
Correct |
23 ms |
31828 KB |
Output is correct |
| 8 |
Correct |
25 ms |
30292 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
22 ms |
31060 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1620 KB |
Output is correct |
| 13 |
Correct |
54 ms |
11652 KB |
Output is correct |
| 14 |
Correct |
32 ms |
8532 KB |
Output is correct |
| 15 |
Correct |
29 ms |
9044 KB |
Output is correct |
| 16 |
Correct |
24 ms |
4196 KB |
Output is correct |
| 17 |
Correct |
122 ms |
20232 KB |
Output is correct |
| 18 |
Correct |
87 ms |
20044 KB |
Output is correct |
| 19 |
Correct |
83 ms |
18772 KB |
Output is correct |
| 20 |
Correct |
77 ms |
17484 KB |
Output is correct |
| 21 |
Correct |
209 ms |
33840 KB |
Output is correct |
| 22 |
Correct |
160 ms |
32696 KB |
Output is correct |
| 23 |
Correct |
243 ms |
27724 KB |
Output is correct |
| 24 |
Correct |
147 ms |
33624 KB |
Output is correct |
| 25 |
Correct |
313 ms |
47400 KB |
Output is correct |
| 26 |
Correct |
1097 ms |
409668 KB |
Output is correct |
| 27 |
Correct |
1048 ms |
191492 KB |
Output is correct |
| 28 |
Correct |
1127 ms |
97788 KB |
Output is correct |
| 29 |
Correct |
1060 ms |
94496 KB |
Output is correct |
| 30 |
Correct |
1053 ms |
125244 KB |
Output is correct |
| 31 |
Correct |
631 ms |
37856 KB |
Output is correct |
| 32 |
Correct |
975 ms |
175020 KB |
Output is correct |
