Submission #1196258

#TimeUsernameProblemLanguageResultExecution timeMemory
1196258marcus06Tracks in the Snow (BOI13_tracks)C++20
100 / 100
581 ms110816 KiB
#include <bits/stdc++.h> using namespace std; using lli = long long; #ifdef LOCAL #include </home/marcus06/mycp/Library/debug.h> #else #define debug(...) #endif const int dx[] = {0, 0, -1, 1}; const int dy[] = {-1, 1, 0, 0}; void solve() { int H, W; cin >> H >> W; vector g(H, vector <char> (W)); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { cin >> g[i][j]; } } auto inside = [&](int u, int v) -> bool { return (u >= 0 && v >= 0 && u < H && v < W); }; vector depth(H, vector <int> (W)); deque <pair <int, int>> dq; depth[0][0] = 1; dq.emplace_back(0, 0); int ans = 0; while (!dq.empty()) { auto [x, y] = dq.front(); dq.pop_front(); ans = max(ans, depth[x][y]); for (int i = 0; i < 4; ++i) { int u = x + dx[i], v = y + dy[i]; if (inside(u, v) && g[u][v] != '.' && depth[u][v] == 0) { depth[u][v] = depth[x][y]; if (g[u][v] == g[x][y]) { dq.emplace_front(u, v); } else { depth[u][v] += 1; dq.emplace_back(u, v); } } } } cout << ans << '\n'; } int main() { std::cin.tie(0)->sync_with_stdio(0); #ifdef LOCAL auto begin = std::chrono::high_resolution_clock::now(); #endif int tt = 1; while (tt--) { solve(); } #ifdef LOCAL auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...