Submission #1197595

#TimeUsernameProblemLanguageResultExecution timeMemory
1197595TahirAliyevTracks in the Snow (BOI13_tracks)C++20
97.81 / 100
1349 ms1114112 KiB
#include <bits/stdc++.h> // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // #define int long long #define ll long long #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; const int oo = 1e9 + 9; const int MAX = 4000 + 5, LOGMAX = 20, B = 441, MOD = 998244353; int n, m; int vis[MAX][MAX][2]; vector<char> ch = {'R', 'F'}; vector<pii> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vector<pii> s; vector<pii> add; string arr[MAX]; void dfs(int x, int y, int t){ vis[x][y][t] = 1; if(!vis[x][y][t^1]) add.push_back({x, y}); for(auto d : dir){ int nx = x + d.first, ny = y + d.second; if(nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny][t] || arr[nx][ny] != ch[t]) continue; dfs(nx, ny, t); } } void solve(){ cin >> n >> m; bool r = 0, f = 0; for(int i = 1; i <= n; i++){ cin >> arr[i]; arr[i] = '%' + arr[i]; } s.push_back({1, 1}); if(arr[1][1] == '.'){ cout << "0\n"; return; } int ans = -1; int t = (arr[1][1] == 'F'); while(s.size()){ for(auto a : s){ if(vis[a.first][a.second][t]){ add.push_back(a); continue; } dfs(a.first, a.second, t); } swap(add, s); add.clear(); ans++; t ^= 1; } cout << ans << '\n'; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...