Submission #810826

#TimeUsernameProblemLanguageResultExecution timeMemory
810826_martynasMaze (JOI23_ho_t3)C++11
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define all(a) (a).begin(), (a).end() using pii = pair<int, int>; const int inf = 1e7; int r, c, n; int sr, sc, gr, gc; vector<string> A; int main() { cin >> r >> c >> n; if(c > r) { swap(r, c); cin >> sc >> sr >> gc >> gr; A = vector<string>(r, string(c, '#')); for(int i = 0; i < c; i++) { string s; cin >> s; for(int j = 0; j < r; j++) { A[j][i] = s[j]; } } } else { cin >> sr >> sc >> gr >> gc; A = vector<string>(r); for(int i = 0; i < c; i++) { cin >> A[i]; } } sr--, sc--, gr--, gc--; // for(int i = 0; i < r; i++) { // cerr << A[i] << "\n"; // } // c < 2500 vector<vector<int>> dist(r, vector<int>(c, inf)); vector<vector<bool>> visited(r, vector<bool>(c)); vector<set<int>> checked(c); deque<pii> deq; vector<pii> dir{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; auto transition = [&](int row, int s, int e, int d) { //cerr << "transit: " << row << " " << s << " " << e << " " << d << "\n"; for(int i = s; i <= e; i++) { // if(dist[row][i] <= d+1) break; if(dist[row][i] > d+1) { dist[row][i] = d+1; deq.push_back({row, i}); } } for(int i = e; i >= s; i--) { //if(dist[row][i] <= d+1) break; if(dist[row][i] > d+1) { dist[row][i] = d+1; deq.push_back({row, i}); } } }; dist[sr][sc] = 0; deq.push_back({sr, sc}); while(!deq.empty()) { int i = deq.front().fi, j = deq.front().se; deq.pop_front(); if(visited[i][j]) continue; visited[i][j] = true; for(auto d : dir) { int ii = i+d.fi, jj = j+d.se; if(ii < 0 || ii >= r || jj < 0 || jj >= c) continue; if(A[ii][jj] == '.' && dist[ii][jj] > dist[i][j]) { dist[ii][jj] = dist[i][j]; deq.push_front({ii, jj}); } } int li = max(0, i-(n-1)), ri = min(n-1, i+(n-1)); if(!checked[j].empty()) { auto it = checked[j].lower_bound(i); if(it == checked[j].end()) { it = prev(it); li = max(li, (*it)+n); } else { ri = min(ri, (*it)-n); if(it != checked[j].begin()) { it = prev(it); li = max(li, (*it)+n); } } } checked[j].insert(i); if(li <= ri) { for(int row = li; row <= ri; row++) { transition(row, max(0, j-n), min(c-1, j+n), dist[i][j]); } } if(i-n >= 0) { transition(i-n, max(0, j-n+1), min(c-1, j+n-1), dist[i][j]); } if(i+n < r) { transition(i+n, max(0, j-n+1), min(c-1, j+n-1), dist[i][j]); } } cout << dist[gr][gc] << "\n"; return 0; }
#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...