#include <bits/stdc++.h>
using namespace std;
int main() {
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 |
32 ms |
1876 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
22 ms |
2516 KB |
Output is correct |
5 |
Correct |
7 ms |
724 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
6 ms |
620 KB |
Output is correct |
11 |
Correct |
6 ms |
976 KB |
Output is correct |
12 |
Correct |
13 ms |
972 KB |
Output is correct |
13 |
Correct |
7 ms |
640 KB |
Output is correct |
14 |
Correct |
8 ms |
724 KB |
Output is correct |
15 |
Correct |
30 ms |
1708 KB |
Output is correct |
16 |
Correct |
35 ms |
1916 KB |
Output is correct |
17 |
Correct |
23 ms |
1492 KB |
Output is correct |
18 |
Correct |
21 ms |
2504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
724 KB |
Output is correct |
2 |
Correct |
141 ms |
8116 KB |
Output is correct |
3 |
Correct |
1158 ms |
79040 KB |
Output is correct |
4 |
Correct |
271 ms |
18732 KB |
Output is correct |
5 |
Correct |
732 ms |
44644 KB |
Output is correct |
6 |
Execution timed out |
2087 ms |
175336 KB |
Time limit exceeded |
7 |
Correct |
4 ms |
852 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
7 ms |
732 KB |
Output is correct |
10 |
Correct |
3 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
852 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
137 ms |
8008 KB |
Output is correct |
14 |
Correct |
81 ms |
4812 KB |
Output is correct |
15 |
Correct |
73 ms |
5140 KB |
Output is correct |
16 |
Correct |
67 ms |
3576 KB |
Output is correct |
17 |
Correct |
382 ms |
20448 KB |
Output is correct |
18 |
Correct |
299 ms |
20008 KB |
Output is correct |
19 |
Correct |
283 ms |
18740 KB |
Output is correct |
20 |
Correct |
259 ms |
17148 KB |
Output is correct |
21 |
Correct |
669 ms |
46128 KB |
Output is correct |
22 |
Correct |
721 ms |
44636 KB |
Output is correct |
23 |
Correct |
704 ms |
38732 KB |
Output is correct |
24 |
Correct |
717 ms |
44972 KB |
Output is correct |
25 |
Correct |
1334 ms |
78880 KB |
Output is correct |
26 |
Correct |
1995 ms |
400656 KB |
Output is correct |
27 |
Execution timed out |
2101 ms |
252784 KB |
Time limit exceeded |
28 |
Execution timed out |
2045 ms |
175260 KB |
Time limit exceeded |
29 |
Execution timed out |
2093 ms |
157940 KB |
Time limit exceeded |
30 |
Execution timed out |
2093 ms |
203336 KB |
Time limit exceeded |
31 |
Correct |
1517 ms |
53508 KB |
Output is correct |
32 |
Execution timed out |
2095 ms |
242064 KB |
Time limit exceeded |