This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=400,M=2e5;
int n,m,k,sx,sy,ex,ey,mvx[]={1,0,-1,0},mvy[]={0,1,0,-1};
vector<vector<int>> dis,p;
vector<vector<bool>> vis;
vector<vector<char>> a;
bool ok(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m && a[x][y]=='.';
}
void bfs1(){
deque<pair<int,int>> dq;
dq.push_front({sx,sy});
dis[sx][sy]=0;
while (!dq.empty()){
int x=dq.front().F,y=dq.front().S;
dq.pop_front();
if (vis[x][y]) continue;
//cout<<x<<' '<<y<<' '<<dis[x][y]<<endl;
vis[x][y]=1;
for (int i=0;i<4;i++){
int nx=mvx[i]+x,ny=mvy[i]+y;
if (!ok(nx,ny)) continue;
if (dis[nx][ny]>dis[x][y]){
dis[nx][ny]=dis[x][y];
dq.push_front({nx,ny});
}
}
for (int i=max(1,x-k);i<=min(n,x+k);i++){
for (int j=max(1,y-k);j<=min(m,y+k);j++){
if (i==x-k && j==y-k) continue;
if (i==x-k && j==y+k) continue;
if (i==x+k && j==y-k) continue;
if (i==x+k && j==y+k) continue;
if (dis[i][j]>dis[x][y]+1){
dis[i][j]=dis[x][y]+1;
dq.push_back({i,j});
}
}
}
//return;
}
return;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m>>k>>sx>>sy>>ex>>ey;
for (int i=0;i<=n+5;i++){
p.pb({});dis.pb({});vis.pb({});a.pb({});
for (int j=0;j<=m+5;j++){
p[i].pb(0);dis[i].pb(INT_MAX);vis[i].pb(0);a[i].pb('#');
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>a[i][j];
if ((2*k+1)*(2*k+1)<=INT_MAX) bfs1();
else ;
cout<<dis[ex][ey]<<endl;
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... |