Submission #1120426

#TimeUsernameProblemLanguageResultExecution timeMemory
1120426raul2008487Tracks in the Snow (BOI13_tracks)C++17
100 / 100
969 ms324400 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define in insert #define fi first #define se second #define vl vector<ll> #define all(v) v.begin(), v.end() #define endl "\n" using namespace std; const int sz = 4005; /// mind this const int MAX = 2e6 + 123; const int BS = 61; const int mod = 998244353; bool used[sz][sz]; char c[sz][sz]; deque<array<ll, 3>> bfs; vector<array<ll, 2>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; void solve(){ ll n, m, i, j, cnt = 0, ans = 0; cin >> n >> m; for(i = 1; i <= n; i++){ for(j = 1; j <= m; j++){ cin >> c[i][j]; if(c[i][j] != '.'){ cnt ++; } } } bfs.push_back({1, 1, 1}); while(cnt){ array<ll, 3> cur = bfs.back(); bfs.pop_back(); if(used[cur[0]][cur[1]]){continue;} // cout << cur[0] << ' ' << cur[1] << ' ' << cur[2] << endl; ans = cur[2]; used[cur[0]][cur[1]] = 1; if(!(--cnt)){break;} for(array<ll, 2> d: dir){ ll nx = cur[0] + d[0], ny = cur[1] + d[1]; if(nx < 1 || nx > n || ny < 1 || ny > m){continue;} if(!used[nx][ny] && c[nx][ny] != '.'){ if(c[nx][ny] == c[cur[0]][cur[1]]){ bfs.pb({nx, ny, cur[2]}); } else{ bfs.push_front({nx, ny, cur[2] + 1}); } } } } cout << ans << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t = 1; // cin >> t; while(t--){ solve(); } } /* 4 4 RRRR .F.R .FFR .RFR */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...