Submission #1157387

#TimeUsernameProblemLanguageResultExecution timeMemory
1157387Marco_EscandonMaze (JOI23_ho_t3)C++20
8 / 100
128 ms12100 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") typedef int ll; #define x first #define y second ll dx[]={1,0,-1,0}; ll dy[]={0,-1,0,1}; ll d1x[]={ 1,1,-1,-1}; ll d1y[]={-1,1, 1,-1}; vector<string> cad; vector<vector<ll>> d; bool inside(pair<ll,ll> a, pair<ll,ll> b, pair<ll,ll> c) { return (a.x<=c.x&&b.x>=c.x&&a.y<=c.y&&b.y>=c.y); } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); ll n,m,k; pair<ll,ll> inicio,fin; cin>>n>>m>>k>>inicio.x>>inicio.y>>fin.x>>fin.y; inicio.x--; inicio.y--; fin.x--; fin.y--; cad.resize(n);d.assign(n,vector<ll>(m,1e8)); for(int i=0; i<n; i++) cin>>cad[i]; deque<pair<ll,ll>> q; q.push_front(inicio); d[inicio.x][inicio.y]=0; while(!q.empty()) { pair<ll,ll> temp1=q.front();q.pop_front(); if(temp1==fin) { cout<<d[fin.x][fin.y]; return 0; } for(int i=0; i<4; i++) { pair<ll,ll> temp=temp1; temp.x+=dx[i];temp.y+=dy[i]; if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]<d[temp.x][temp.y]&&cad[temp.x][temp.y]=='.') { d[temp.x][temp.y]=d[temp1.x][temp1.y]; if(temp==fin) { cout<<d[fin.x][fin.y]; return 0; } q.push_front(temp); } } queue<pair<ll,ll>> q2; q2.push(temp1); while(!q2.empty()) { pair<ll,ll> temp2=q2.front();q2.pop(); for(int i=0; i<4; i++) { pair<ll,ll> temp=temp2; temp.x+=dx[i];temp.y+=dy[i]; if(inside({0,0},{n-1,m-1},temp)&&inside({temp1.x-k,temp1.y-k},{temp1.x+k,temp1.y+k},temp)&&abs(temp1.x-temp.x)+abs(temp1.y-temp.y)<2*k&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y]) { d[temp.x][temp.y]=d[temp1.x][temp1.y]+1; q2.push(temp); q.push_back(temp); } } } //for(int i=0; i<n; i++){ // for(int j=0; j<m; j++) // cout<<d[i][j]<<" "; // cout<<"\n"; //} //cout<<"\n";//if(inside(,,fin)&&d[temp1.x][temp1.y]+1<d[fin.x][fin.y]) } cout<<d[fin.x][fin.y]; 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...