Submission #1203511

#TimeUsernameProblemLanguageResultExecution timeMemory
1203511newsboyTracks in the Snow (BOI13_tracks)C++20
100 / 100
496 ms210116 KiB
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <iomanip> #include <set> #include <map> #include <numeric> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <bitset> #include <queue> #include <deque> #include <stack> #include <cmath> #include <tuple> #include <cassert> #include <list> #include <random> #include <initializer_list> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; constexpr ld inf = 1e18; constexpr ll N = 15; constexpr ll MIN = -inf; constexpr ll MAX = inf; struct Point { ll x, y; }; void solve() { ll n, m; cin >> n >> m; vector<string> a(n); for (ll i = 0; i < n; ++i) { cin >> a[i]; } auto ok = [&](ll x, ll y) -> bool { return x > -1 && x < n && y > -1 && y < m && a[x][y] != '.'; }; deque<Point> q; vector<vector<ll>> d(n, vector<ll> (m, -1)); vector<ll> dx{ 1, -1, 0, 0 }, dy{ 0, 0, 1, -1 }; q.push_back({ 0, 0 }); d[0][0] = 0; ll ans = 0; while (!q.empty()) { Point v = q.front(); q.pop_front(); ans = max(ans, d[v.x][v.y]); for (ll i = 0; i < 4; ++i) { ll x = v.x + dx[i], y = v.y + dy[i]; if (ok(x, y) && d[x][y] == -1) { if (a[x][y] == a[v.x][v.y]) { d[x][y] = d[v.x][v.y]; q.push_front({ x, y }); } else { d[x][y] = d[v.x][v.y] + 1; q.push_back({ x, y }); } } } } cout << ans + 1 << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; /*cin >> t;*/ while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...