#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main (void) {
iostream::sync_with_stdio(false);
cin.tie(0);
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int N, M;
cin >> N >> M;
vector<string> grid(N);
for (int i = 0; i < N; i++)
cin >> grid[i];
vector<vector<int>> dist(N, vector<int>(M, 1e9));
deque<vector<int>> bfs;
bfs.push_back({0, 0, 1});
int ans = 0;
while (!bfs.empty()) {
int x = bfs.front()[0], y = bfs.front()[1], d = bfs.front()[2];
bfs.pop_front();
dist[x][y] = d;
ans = max(ans, d);
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M)
continue;
if (dist[nx][ny] < 1e9 || grid[nx][ny] == '.')
continue;
vector<int> next = {nx, ny, d};
if (grid[x][y] != grid[nx][ny]) {
next[2]++;
bfs.push_back(next);
} else
bfs.push_front(next);
}
}
/*for (auto x: dist) {
for (auto y: x) {
cout << y << " ";
}
cout << endl;
}*/
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
2908 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
19 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
860 KB |
Output is correct |
6 |
Correct |
0 ms |
360 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
360 KB |
Output is correct |
10 |
Correct |
3 ms |
908 KB |
Output is correct |
11 |
Correct |
5 ms |
1372 KB |
Output is correct |
12 |
Correct |
13 ms |
1576 KB |
Output is correct |
13 |
Correct |
3 ms |
856 KB |
Output is correct |
14 |
Correct |
3 ms |
860 KB |
Output is correct |
15 |
Correct |
25 ms |
2396 KB |
Output is correct |
16 |
Correct |
34 ms |
2904 KB |
Output is correct |
17 |
Correct |
14 ms |
1880 KB |
Output is correct |
18 |
Correct |
19 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
856 KB |
Output is correct |
2 |
Correct |
97 ms |
9552 KB |
Output is correct |
3 |
Correct |
361 ms |
89292 KB |
Output is correct |
4 |
Correct |
69 ms |
21324 KB |
Output is correct |
5 |
Correct |
186 ms |
50220 KB |
Output is correct |
6 |
Execution timed out |
2073 ms |
304776 KB |
Time limit exceeded |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
4 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
87 ms |
9532 KB |
Output is correct |
14 |
Correct |
45 ms |
5724 KB |
Output is correct |
15 |
Correct |
17 ms |
6236 KB |
Output is correct |
16 |
Correct |
45 ms |
4188 KB |
Output is correct |
17 |
Correct |
203 ms |
23388 KB |
Output is correct |
18 |
Correct |
86 ms |
22764 KB |
Output is correct |
19 |
Correct |
69 ms |
21336 KB |
Output is correct |
20 |
Correct |
84 ms |
19548 KB |
Output is correct |
21 |
Correct |
220 ms |
52040 KB |
Output is correct |
22 |
Correct |
185 ms |
50312 KB |
Output is correct |
23 |
Correct |
464 ms |
43860 KB |
Output is correct |
24 |
Correct |
157 ms |
50604 KB |
Output is correct |
25 |
Correct |
402 ms |
89468 KB |
Output is correct |
26 |
Execution timed out |
2086 ms |
743992 KB |
Time limit exceeded |
27 |
Execution timed out |
2085 ms |
383500 KB |
Time limit exceeded |
28 |
Execution timed out |
2076 ms |
298292 KB |
Time limit exceeded |
29 |
Execution timed out |
2087 ms |
279776 KB |
Time limit exceeded |
30 |
Execution timed out |
2076 ms |
328420 KB |
Time limit exceeded |
31 |
Correct |
1729 ms |
59716 KB |
Output is correct |
32 |
Execution timed out |
2065 ms |
350068 KB |
Time limit exceeded |