Submission #1120214

#TimeUsernameProblemLanguageResultExecution timeMemory
1120214HasanV11010238Tracks in the Snow (BOI13_tracks)C++17
75.94 / 100
2126 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long long #define INF 1000000000 vector<vector<vector<int>>> v; int bfs(int n, int st){ vector<int> di(n, INF); deque<int> q; di[st] = 0; q.push_back(st); while (!q.empty()){ int x = q.front(); q.pop_front(); for (auto el : v[x]){ if (di[el[0]] > di[x] + el[1]){ di[el[0]] = di[x] + el[1]; if (el[1] == 0){ q.push_front(el[0]); } else{ q.push_back(el[0]); } } } } int ans = 0; for (int i = 0; i < n; i++){ if (di[i] == INF) continue; ans = max(ans, di[i]); } return ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin>>n>>m; map<char, int> ma; ma['F'] = 0; ma['R'] = 1; v.resize(n * m); vector<string> s(n); for (int i = 0; i < n; i++){ cin>>s[i]; for (int j = 0; j < m; j++){ if (s[i][j] == '.') continue; int v1 = i * m + j; if (i != 0 && s[i - 1][j] != '.'){ int v2 = (i - 1) * m + j; v[v1].push_back({v2, ma[s[i][j]] ^ ma[s[i - 1][j]]}); v[v2].push_back({v1, ma[s[i][j]] ^ ma[s[i - 1][j]]}); } if (j != 0 && s[i][j - 1] != '.'){ int v2 = i * m + j - 1; v[v1].push_back({v2, ma[s[i][j]] ^ ma[s[i][j - 1]]}); v[v2].push_back({v1, ma[s[i][j]] ^ ma[s[i][j - 1]]}); } } } cout<<bfs(n * m, 0) + 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...