Submission #1229462

#TimeUsernameProblemLanguageResultExecution timeMemory
1229462chikien2009Tracks in the Snow (BOI13_tracks)C++20
100 / 100
536 ms132512 KiB
#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; int h, w, f[4000][4000], a, b, res, x, y; string s[4000]; bool check[4000][4000]; deque<pair<int, int>> dq; int main() { setup(); cin >> h >> w; for (int i = 0; i < h; ++i) { cin >> s[i]; for (int j = 0; j < w; ++j) { f[i][j] = 1e9; } } dq.push_back({0, 0}); f[0][0] = 1; while (!dq.empty()) { a = dq.front().first; b = dq.front().second; dq.pop_front(); if (check[a][b]) { continue; } check[a][b] = true; res = max(res, f[a][b]); for (int i = 0; i < 4; ++i) { x = a + dx[i]; y = b + dy[i]; if (0 <= x && x < h && 0 <= y && y < w && !check[x][y] && s[x][y] != '.') { if (f[x][y] > f[a][b] + (s[x][y] != s[a][b])) { f[x][y] = f[a][b] + (s[x][y] != s[a][b]); if (s[x][y] != s[a][b]) { dq.push_back({x, y}); } else { dq.push_front({x, y}); } } } } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...