#include <bits/stdc++.h>
using namespace std;
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
int h, w;
cin >> h >> w;
vector<vector<char> > graph(h, vector<char>(w, 0));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> graph[i][j];
}
}
deque<vector<int> > bfs;
bfs.push_back({0, 0});
vector<vector<int> > dist(h, vector<int>(w, -1));
dist[0][0] = 1;
int ans = 0;
vector<pair<int, int> > vec = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!bfs.empty()) {
auto current = bfs.front();
bfs.pop_front();
ans = max(ans, dist[current[0]][current[1]]);
// cout << current[0] << current[1] << dist[current[0]][current[1]] << endl;
for (pair<int, int> val: vec) {
int newx = current[0] + val.first;
int newy = current[1] + val.second;
if (newx >= 0 &&
newx < h &&
newy < w &&
newy >= 0) {
if (graph[newx][newy] == '.' || dist[newx][newy] != -1) continue;
if (graph[newx][newy] ==
graph[current[0]][current[1]]) {
dist[newx][newy] = dist[current[0]][current[1]];
bfs.push_front({newx, newy});
} else {
bfs.push_back({newx, newy});
dist[newx][newy] = dist[current[0]][current[1]] + 1;
}
}
}
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
1948 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
16 ms |
2556 KB |
Output is correct |
5 |
Correct |
3 ms |
724 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
596 KB |
Output is correct |
11 |
Correct |
7 ms |
980 KB |
Output is correct |
12 |
Correct |
10 ms |
980 KB |
Output is correct |
13 |
Correct |
4 ms |
724 KB |
Output is correct |
14 |
Correct |
4 ms |
724 KB |
Output is correct |
15 |
Correct |
21 ms |
1744 KB |
Output is correct |
16 |
Correct |
24 ms |
1936 KB |
Output is correct |
17 |
Correct |
14 ms |
1608 KB |
Output is correct |
18 |
Correct |
15 ms |
2552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
852 KB |
Output is correct |
2 |
Correct |
88 ms |
8156 KB |
Output is correct |
3 |
Correct |
515 ms |
78948 KB |
Output is correct |
4 |
Correct |
113 ms |
18752 KB |
Output is correct |
5 |
Correct |
374 ms |
44560 KB |
Output is correct |
6 |
Correct |
1906 ms |
175220 KB |
Output is correct |
7 |
Correct |
3 ms |
852 KB |
Output is correct |
8 |
Correct |
4 ms |
852 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
3 ms |
852 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
82 ms |
8156 KB |
Output is correct |
14 |
Correct |
47 ms |
4868 KB |
Output is correct |
15 |
Correct |
33 ms |
5204 KB |
Output is correct |
16 |
Correct |
42 ms |
3604 KB |
Output is correct |
17 |
Correct |
239 ms |
20468 KB |
Output is correct |
18 |
Correct |
151 ms |
20032 KB |
Output is correct |
19 |
Correct |
122 ms |
18884 KB |
Output is correct |
20 |
Correct |
123 ms |
17260 KB |
Output is correct |
21 |
Correct |
316 ms |
46032 KB |
Output is correct |
22 |
Correct |
367 ms |
44524 KB |
Output is correct |
23 |
Correct |
397 ms |
38584 KB |
Output is correct |
24 |
Correct |
330 ms |
44888 KB |
Output is correct |
25 |
Correct |
712 ms |
78908 KB |
Output is correct |
26 |
Correct |
1565 ms |
400636 KB |
Output is correct |
27 |
Correct |
1696 ms |
253204 KB |
Output is correct |
28 |
Correct |
1903 ms |
175888 KB |
Output is correct |
29 |
Correct |
1953 ms |
158172 KB |
Output is correct |
30 |
Correct |
1836 ms |
203612 KB |
Output is correct |
31 |
Correct |
1172 ms |
53784 KB |
Output is correct |
32 |
Correct |
1566 ms |
242432 KB |
Output is correct |