#include <bits/stdc++.h>
using namespace std;
int main() {
#define int long long
ios::sync_with_stdio(false);
cin.tie(0);
int h, w;
cin >> h >> w;
/*
*We can use the following greedy strategy to find our answer:
Consider the graph with an edge between each pair of adjacent cells with
tracks, where the weight is 0 if the tracks are the same and 1 otherwise.
The answer is simply the longest shortest-path from the top left cell. This
is because going from one track to another same one is like not leaving a
node (hence the cost is $0$), while going from one track to a different one
is like traversing the edge between two nodes (hence the cost is $1$). Since
the weight of each edge is either 0 or 1 and we want the shortest paths from
the top left cell to each other cell, we can apply 0/1 BFS. The time
complexity of this solution is $\mathcal O(NM)$.
*/
//
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
vector<string> grid(h);
for (int i = 0; i < h; i++) {
std::cin >> grid[i];
}
vector<vector<int>> lengths(h, vector<int>(w, LONG_LONG_MAX));
auto works = [&](int x, int y) {
return y >= 0 && y < h && x >= 0 && x < w && grid[y][x] != '.';
};
deque<pair<int, int>> bfs;
bfs.push_back({0, 0});
lengths[0][0] = 1;
while (!bfs.empty()) {
auto front = bfs.front();
bfs.pop_front();
for (int k = 0; k < 4; k++) {
int x = front.first + dx[k];
int y = front.second + dy[k];
if (works(x, y) && lengths[y][x] == LONG_LONG_MAX) {
if (grid[y][x] == grid[front.second][front.first]) {
lengths[y][x] = lengths[front.second][front.first];
bfs.push_front({x, y});
} else {
lengths[y][x] = lengths[front.second][front.first] + 1;
bfs.push_back({x, y});
}
}
}
}
int ans = 0;
for (auto i : lengths)
for (auto j : i) {
if (j != LONG_LONG_MAX)
ans = max(j, ans);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2904 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
460 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1396 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 15 |
Correct |
7 ms |
2908 KB |
Output is correct |
| 16 |
Correct |
8 ms |
2880 KB |
Output is correct |
| 17 |
Correct |
6 ms |
2652 KB |
Output is correct |
| 18 |
Correct |
4 ms |
2392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
30 ms |
15968 KB |
Output is correct |
| 3 |
Correct |
178 ms |
159160 KB |
Output is correct |
| 4 |
Correct |
56 ms |
37456 KB |
Output is correct |
| 5 |
Correct |
135 ms |
89684 KB |
Output is correct |
| 6 |
Correct |
490 ms |
185496 KB |
Output is correct |
| 7 |
Correct |
1 ms |
860 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1012 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1128 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
29 ms |
15972 KB |
Output is correct |
| 14 |
Correct |
17 ms |
9308 KB |
Output is correct |
| 15 |
Correct |
13 ms |
10332 KB |
Output is correct |
| 16 |
Correct |
14 ms |
7004 KB |
Output is correct |
| 17 |
Correct |
77 ms |
40528 KB |
Output is correct |
| 18 |
Correct |
66 ms |
40044 KB |
Output is correct |
| 19 |
Correct |
54 ms |
37456 KB |
Output is correct |
| 20 |
Correct |
43 ms |
34384 KB |
Output is correct |
| 21 |
Correct |
106 ms |
92500 KB |
Output is correct |
| 22 |
Correct |
132 ms |
89680 KB |
Output is correct |
| 23 |
Correct |
150 ms |
77244 KB |
Output is correct |
| 24 |
Correct |
104 ms |
90452 KB |
Output is correct |
| 25 |
Correct |
422 ms |
159380 KB |
Output is correct |
| 26 |
Correct |
295 ms |
222184 KB |
Output is correct |
| 27 |
Correct |
364 ms |
194332 KB |
Output is correct |
| 28 |
Correct |
482 ms |
185728 KB |
Output is correct |
| 29 |
Correct |
477 ms |
186088 KB |
Output is correct |
| 30 |
Correct |
441 ms |
185344 KB |
Output is correct |
| 31 |
Correct |
352 ms |
102700 KB |
Output is correct |
| 32 |
Correct |
333 ms |
190188 KB |
Output is correct |
