#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);
}
}
for(int i=0; i<k; i++)
for(int j=0; j<4; j++)
{
pair<ll,ll> temp=temp1;
temp.x+=d1x[j]*i;temp.y+=d1y[j]*k;
if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
{
d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
q.push_back(temp);
}
temp=temp1;
temp.y-=d1x[j]*i;temp.x+=d1y[j]*k;
if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
{
d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
q.push_back(temp);
}
}
if(inside({temp1.x-k,temp1.y-k},{temp1.x+k,temp1.y+k},fin)&&d[temp1.x][temp1.y]+1<d[fin.x][fin.y])
{
d[fin.x][fin.y]=d[temp1.x][temp1.y]+1;
q.push_back(fin);
}
}
cout<<d[fin.x][fin.y];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |