Submission #1197631

#TimeUsernameProblemLanguageResultExecution timeMemory
1197631TahirAliyevTracks in the Snow (BOI13_tracks)C++20
100 / 100
655 ms318192 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]; vector<char> ch = {'R', 'F'}; vector<pii> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; string arr[MAX]; void solve(){ cin >> n >> m; bool r = 0, f = 0; for(int i = 1; i <= n; i++){ cin >> arr[i]; arr[i] = '%' + arr[i]; } if(arr[1][1] == '.'){ cout << "0\n"; return; } int ans = 0; deque<pii> q; q.push_back({1, 1}); char pr = '$'; while(q.size()){ pii a = q.front(); q.pop_front(); if(vis[a.first][a.second]) continue; vis[a.first][a.second] = 1; if(arr[a.first][a.second] != pr) ans++; pr = arr[a.first][a.second]; for(auto d : dir){ int nx = a.first + d.first; int ny = a.second + d.second; if(!(1 <= nx && nx <= n && 1 <= ny && ny <= m) || (arr[nx][ny] == '.')) continue; if(arr[nx][ny] == pr) q.push_front({nx, ny}); else q.push_back({nx, ny}); } } 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...