제출 #716289

#제출 시각아이디문제언어결과실행 시간메모리
716289nima_aryanTracks in the Snow (BOI13_tracks)C++17
100 / 100
620 ms111952 KiB
#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); static int H, W; cin >> H >> W; static vector<string> snow(H); for (int i = 0; i < H; ++i) { cin >> snow[i]; } const int inf = (int) 1e9; vector dist(H, vector<int>(W, inf)); struct cell { int x, y; bool valid() { return x >= 0 && x < H && y >= 0 && y < W && snow[x][y] != '.'; }; }; deque<cell> dq; auto ad = [&](cell c, int add, int extra = 0) { if (extra) { dq.push_back(c); } else { dq.push_front(c); } dist[c.x][c.y] = add + extra; }; ad(cell{0, 0}, 1); vector<int> dx{1, -1, 0, 0}; vector<int> dy{0, 0, 1, -1}; int ans = 1; while (!dq.empty()) { auto c = dq.front(); dq.pop_front(); ans = max(ans, dist[c.x][c.y]); for (int i = 0; i < 4; ++i) { int x = c.x + dx[i], y = c.y + dy[i]; auto newc = cell{x, y}; if (!newc.valid() || dist[x][y] < inf) { continue; } ad(newc, dist[c.x][c.y], (int) (snow[x][y] != snow[c.x][c.y])); } } 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...