This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int H, W;
cin >> H >> W;
vector<string> grid(H);
for (int i = 0; i < H; ++i) {
cin >> grid[i];
}
auto id = [&](int i, int j) {
return W * i + j;
};
auto di = [&](int i) {
return make_pair(i / W, i % W);
};
auto get = [&](int node) {
auto [i, j] = di(node);
return grid[i][j];
};
const int N = H * W;
vector<vector<int>> graph(N);
auto add_edge = [&](int a, int b) {
if (get(a) == '.' || get(b) == '.') {
return;
}
graph[a].push_back(b);
graph[b].push_back(a);
};
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
if (j + 1 < W) {
add_edge(id(i, j), id(i, j + 1));
}
if (i + 1 < H) {
add_edge(id(i, j), id(i + 1, j));
}
}
}
const int inf = (int) 1e9;
vector<int> dist(N, inf);
deque<int> dq;
auto ad = [&](int node, int add, int extra = 0) {
if (extra) {
dq.push_back(node);
}
else {
dq.push_front(node);
}
dist[node] = add + extra;
};
ad(0, 1);
int ans = 1;
while (!dq.empty()) {
int node = dq.front();
dq.pop_front();
ans = max(ans, dist[node]);
for (int neighbor : graph[node]) {
if (dist[neighbor] < inf) {
continue;
}
ad(neighbor, dist[node], get(node) != get(neighbor));
}
}
cout << ans << '\n';
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message (stderr)
tracks.cpp: In lambda function:
tracks.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | auto [i, j] = di(node);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |