제출 #1241806

#제출 시각아이디문제언어결과실행 시간메모리
1241806GeforgsMaze (JOI23_ho_t3)C++20
27 / 100
127 ms47516 KiB
#include <iostream> #include <iomanip> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <queue> #include <map> #include <unordered_map> #include <stack> #include <bitset> #include <string> #include <cstring> #include <iterator> #include <random> #define ll long long #define ld long double #define inf (ll)(2*1e18) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define pb push_back #define endl "\n" using namespace std; ll get(ll x, vector<ll>& parent){ if(parent[x] == x) return x; return parent[x] = get(parent[x], parent); } void unite(ll x, ll y, vector<ll>& parent){ x = get(x, parent); y = get(y, parent); parent[x] = y; } void push(ll pos, ll r, ll c, vector<ll>& dis, queue<ll>& q){ ll x = pos/c, y = pos%c; if(x < r-1 and dis[pos + c] > dis[pos]){ dis[pos + c] = dis[pos]; q.push(pos + c); } if(x > 0 and dis[pos - c] > dis[pos]){ dis[pos - c] = dis[pos]; q.push(pos - c); } if(y < c-1 and dis[pos+1] > dis[pos]){ dis[pos+1] = dis[pos]; q.push(pos+1); } if(y > 0 and dis[pos-1] > dis[pos]){ dis[pos-1] = dis[pos]; q.push(pos-1); } } void push2(ll pos, ll r, ll c, ll n, vector<ll>& dis, queue<ll>& q, vector<ll>& parent, vector<ll>& parent2){ ll x = pos/c, y = pos%c, curX, curY, nextX, nextY, nextPos, endPos; curX = max(0ll, x - n); curY = max(0ll, y - n + 1); nextY = min(c-1, curY + 2*n - 2); nextPos = curX*c + curY; nextPos = get(nextPos, parent); endPos = curX*c + nextY; while(true){ if(nextPos >= endPos){ if(dis[endPos] > dis[pos] + 1){ dis[endPos] = dis[pos] + 1; q.push(endPos); } break; } if(dis[nextPos] > dis[pos] + 1){ dis[nextPos] = dis[pos] + 1; q.push(nextPos); } unite(nextPos, nextPos+1, parent); nextPos = get(nextPos, parent); } curX = min(r-1, x + n); nextPos = curX*c + curY; nextPos = get(nextPos, parent); endPos = curX*c + nextY; while(true){ if(nextPos >= endPos){ if(dis[endPos] > dis[pos] + 1){ dis[endPos] = dis[pos] + 1; q.push(endPos); } break; } if(dis[nextPos] > dis[pos] + 1){ dis[nextPos] = dis[pos] + 1; q.push(nextPos); } unite(nextPos, nextPos+1, parent); nextPos = get(nextPos, parent); } curX = max(0ll, x - n + 1); curY = max(0ll, y - n); nextX = min(r-1, curX + 2*n - 2); nextPos = curX*c + curY; nextPos = get(nextPos, parent2); endPos = nextX*c + curY; while(true){ if(nextPos >= endPos){ if(dis[endPos] > dis[pos] + 1){ dis[endPos] = dis[pos] + 1; q.push(endPos); } break; } if(dis[nextPos] > dis[pos] + 1){ dis[nextPos] = dis[pos] + 1; q.push(nextPos); } unite(nextPos, nextPos+c, parent2); nextPos = get(nextPos, parent2); } curY = min(c-1, y + n); nextPos = curX*c + curY; nextPos = get(nextPos, parent2); endPos = nextX*c + curY; while(true){ if(nextPos >= endPos){ if(dis[endPos] > dis[pos] + 1){ dis[endPos] = dis[pos] + 1; q.push(endPos); } break; } if(dis[nextPos] > dis[pos] + 1){ dis[nextPos] = dis[pos] + 1; q.push(nextPos); } unite(nextPos, nextPos+c, parent2); nextPos = get(nextPos, parent2); } } void solve(){ ll r, c, n, startR, startC, finishR, finishC, i, j, pos, distance=0; char x; cin>>r>>c>>n>>startR>>startC>>finishR>>finishC; --startR; --startC; --finishR; --finishC; vector<ll> a(r*c); vector<ll> dis(r*c, inf); vector<ll> parent(r*c); vector<ll> parent2(r*c); for(i=0;i<r;++i){ for(j=0;j<c;++j){ cin>>x; a[i*c + j] = x == '.'; parent[i*c + j] = i*c + j; parent2[i*c + j] = i*c + j; } } queue<ll> q1, q2; dis[startR*c + startC] = 0; q1.push(startR*c + startC); while(!q1.empty()){ while(!q1.empty()){ pos = q1.front(); q1.pop(); if(dis[pos] < distance) continue; if(a[pos]){ push(pos, r, c, dis, q1); }else{ push2(pos, r, c, n, dis, q2, parent, parent2); } } ++distance; swap(q1, q2); } for(i=max(0ll, finishR-n+1);i<min(r-1, finishR+n-1);++i){ for(j=max(0ll, finishC-n+1);j<min(c-1, finishC+n-1);++j){ dis[finishR*c + finishC] = min(dis[finishR*c + finishC], dis[i*c+j] + 1); } } cout<<dis[finishR*c + finishC]<<endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); srand(time(nullptr)); ll t=1; // cin>>t; for(;t>0;--t){ solve(); } 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...