Submission #1245524

#TimeUsernameProblemLanguageResultExecution timeMemory
1245524nanh0607Tracks in the Snow (BOI13_tracks)C++20
100 / 100
643 ms110828 KiB
#include <bits/stdc++.h> #include <cstdlib> using namespace std; using ll = long long; using str = string; using pii = pair<int, int>; using pil = pair<int, ll>; using pll = pair<ll, ll>; #define FOR(i, l, r) for (int i=l; i<=r; i++) #define FOR2(i, l, r) for (int i=l; i>=r; i--) #define ALL(v) v.begin(), v.end() #define fi first #define se second #define ce cout << endl #define pb push_back #define pf push_front #define pob pop_back #define pof pop_front #define eb emplace_back #define ef emplace_front #define ep emplace const ll MOD = 998244353; const int INF = 1e9; const int LOG = 60; const double MAX = 1e9; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // north, south, east, weast void solve() { int n, m; cin >> n >> m; vector<vector<char>> meadow (n, vector<char> (m)); FOR(i, 0, n-1) FOR(j, 0, m-1) cin >> meadow[i][j]; function<bool(int x, int y)> inside = [&] (int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && meadow[x][y] != '.'; }; vector<vector<int>> depth(n, vector<int> (m, -1)); deque<pii> dq; depth[0][0] = 0; dq.eb(0, 0); int res = 0; while (!dq.empty()) { auto [x1, y1] = dq.back(); dq.pob(); res = max(res, depth[x1][y1]); FOR(i, 0, 3) { int x2 = x1 + dx[i], y2 = y1 + dy[i]; if (!inside(x2, y2) || depth[x2][y2] != -1) continue; if (meadow[x2][y2] == meadow[x1][y1]) { depth[x2][y2] = depth[x1][y1]; dq.eb(x2, y2); } else { depth[x2][y2] = depth[x1][y1]+1; dq.ef(x2, y2); } } } cout << res+1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("movie.in", "r", stdin); // freopen("movie.out", "w", stdout); int t = 1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...