Submission #1157492

#TimeUsernameProblemLanguageResultExecution timeMemory
1157492Marco_EscandonMaze (JOI23_ho_t3)C++20
35 / 100
2095 ms176092 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") typedef int ll; #define x first #define y second ll dx[]={1,-1,0,0}; ll dy[]={0,0,-1,1}; ll n,m,k; vector<string> cad; vector<vector<ll>> d,v,v3; bool inside(pair<ll,ll> c) { pair<ll,ll> a={0,0}; pair<ll,ll> b={n-1,m-1}; 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); 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); for(int i=0; i<n; i++) cin>>cad[i]; d.assign(n,vector<ll>(m,1e8)); v.assign(n,vector<ll>(m,1e8)); v3.assign(n,vector<ll>(m,1e8)); queue<pair<ll,ll>> q,q2,q3; q.push(inicio); d[inicio.x][inicio.y]=0; while(!q.empty()) { // expand same component ll asd=d[q.front().x][q.front().y]; while(!q.empty()) { pair<ll,ll> node=q.front();q.pop(); //cerr<<node.x<<node.y<<" "; for(int i=0; i<4; i++) { pair<ll,ll> node1={node.x+dx[i],node.y+dy[i]}; if(!(inside(node1)&&d[node1.x][node1.y]==1e8)) continue; if(cad[node1.x][node1.y]=='.') { d[node1.x][node1.y]=d[node.x][node.y]; q.push(node1); } else { v[node1.x][node1.y]=0; q2.push(node1); } } } //vertical expand while(!q2.empty()) { pair<ll,ll> node=q2.front();q2.pop(); q3.push(node); v3[node.x][node.y]=0; if(v[node.x][node.y]!=k-1) for(int i=0; i<2; i++) { pair<ll,ll> node1={node.x+dx[i],node.y+dy[i]}; if(!(inside(node1)&&d[node1.x][node1.y]==1e8&&v[node1.x][node1.y]==1e8)) continue; v[node1.x][node1.y]=v[node.x][node.y]+1; q2.push(node1); } } //horizontal expand while(!q3.empty()) { pair<ll,ll> node=q3.front();q3.pop(); q.push(node); d[node.x][node.y]=asd+1; if(v3[node.x][node.y]!=k-1) for(int i=2; i<4; i++) { pair<ll,ll> node1={node.x+dx[i],node.y+dy[i]}; if(!(inside(node1)&&d[node1.x][node1.y]==1e8&&v3[node1.x][node1.y]==1e8)) continue; v3[node1.x][node1.y]=v3[node.x][node.y]+1; q3.push(node1); } } } 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...