Submission #1043814

#TimeUsernameProblemLanguageResultExecution timeMemory
1043814Shayan86Maze (JOI23_ho_t3)C++14
8 / 100
76 ms20200 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; typedef unsigned long long ull; #define Mp make_pair #define sep ' ' #define endl '\n' #define F first #define S second #define pb push_back #define all(x) (x).begin(),(x).end() #define kill(res) cout << res << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout); #define lid (id*2) #define rid (id*2+1) #define mid ((l+r)/2) const ll N = 6e6 + 50; const ll inf = 1e9; ll n, m, k, cc, s[2], t[2]; int ax[4] = {-1, 0, 1, 0}, ay[4] = {0, -1, 0, 1}; vector<vector<char>> a; vector<vector<int>> dist; bool check(int i, int j){ return (i >= 0 && j >= 0 && i < n & j < m); } void bfs(int s1, int s2){ dist[s1][s2] = 0; deque<pair<pii, pii>> dq; dq.push_back({{s1, s2}, {0, 0}}); while(!dq.empty()){ auto [v, d] = dq.front(); dq.pop_front(); for(int i = 0; i < 4; i++){ int ip = v.F + ax[i], jp = v.S + ay[i]; if(!check(ip, jp)) continue; if(abs(ax[i]) <= d.F && abs(ay[i]) <= d.S && dist[ip][jp] > dist[v.F][v.S]){ dist[ip][jp] = dist[v.F][v.S]; dq.push_front({{ip, jp}, {d.F - abs(ax[i]), d.S - abs(ay[i])}}); } else if(a[ip][jp] == '.' && dist[ip][jp] > dist[v.F][v.S]){ dist[ip][jp] = dist[v.F][v.S]; dq.push_front({{ip, jp}, {0, 0}}); } if(check(ip, jp) && dist[ip][jp] > dist[v.F][v.S] + 1){ dist[ip][jp] = dist[v.F][v.S] + 1; dq.push_back({{ip, jp}, {k-1, k-1}}); } } } } int main(){ fast_io; cin >> n >> m >> k; a.resize(n, vector<char>(m)); dist.resize(n, vector<int>(m, inf)); cin >> s[0] >> s[1] >> t[0] >> t[1]; s[0]--; s[1]--; t[0]--; t[1]--; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j]; bfs(s[0], s[1]); cout << dist[t[0]][t[1]]; }

Compilation message (stderr)

Main.cpp: In function 'bool check(int, int)':
Main.cpp:40:35: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   40 |     return (i >= 0 && j >= 0 && i < n & j < m);
      |                                 ~~^~~
Main.cpp: In function 'void bfs(int, int)':
Main.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         auto [v, d] = dq.front();
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...