제출 #507349

#제출 시각아이디문제언어결과실행 시간메모리
507349FalconTracks in the Snow (BOI13_tracks)C++17
100 / 100
774 ms59608 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define rep(i, N) for (int i = 0; i < (N); ++i) #define rrep(i, N) for (int i = (N)-1; i >= 0; --i) #define rep1(i, N) for (int i = 1; i <= (N); ++i) #define rep2(i, s, e) for (int i = (s); i <= (e); ++i) #ifdef DEBUG #define debug(x...) \ do { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } while (false) #else #define debug(...) 42 #endif template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } template<typename T, size_t dim> class tensor { private: vector<tensor<T, dim - 1>> v; public: template<typename... V> tensor(size_t d, V... ds): v(d, tensor<T, dim - 1>(ds...)) {} tensor<T, dim - 1>& operator[](size_t i) { return v[i]; } size_t size() { return v.size(); } auto begin() { return v.begin(); } auto end() { return v.end(); } }; template<typename T> class tensor<T, 0> { private: T v; public: tensor(T a = T{}): v{a} {} operator T() { return v; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; vector<string> grid(H); rep(i, H) cin >> grid[i]; tensor<bool, 2> vis(H, W); int ans{}; queue<pair<int, int>> a, b; b.push({0, 0}); vis[0][0] = true; auto check = [&](int i, int j, char c) -> void { if (i < 0 || j < 0 || i >= H || j >= W) return; if (grid[i][j] == '.' || vis[i][j]) return; vis[i][j] = true; if (grid[i][j] == c) a.push({i, j}); else b.push({i, j}); }; while (!b.empty()) { ++ans; swap(a, b); while (!a.empty()) { auto [i, j] = a.front(); check(i + 1, j, grid[i][j]); check(i - 1, j, grid[i][j]); check(i, j + 1, grid[i][j]); check(i, j - 1, grid[i][j]); a.pop(); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...