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=1300;
int n,m,k,sx,sy,ex,ey,mvx[]={1,0,-1,0},mvy[]={0,1,0,-1};
bool ok(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m;
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m>>k>>sx>>sy>>ex>>ey;
int dis[n+2][m+2],p[n+2][m+2];
char a[n+2][m+2];
bool vis[n+2][m+2];
for (int i=0;i<n+2;i++){
for (int j=0;j<m+2;j++){
vis[i][j]=0;
dis[i][j]=INT_MAX;
p[i][j]=0;
if (i && i<=n && j && j<=m) cin>>a[i][j];
}
}
if ((2*k+1)*(2*k+1)<=N){
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) || a[x][y]!='.') 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});
}
}
}
}
}
else{
vector<pair<int,int>> q;
dis[sx][sy]=0;
vis[sx][sy]=1;
q.pb({sx,sy});
for (int t=0;t<INT_MAX;t++){
for (int i=0;i<q.size();i++){
int x=q[i].F,y=q[i].S;
dis[x][y]=t;
for (int j=0;j<4;j++){
int nx=x+mvx[j],ny=y+mvy[j];
if (vis[nx][ny] || !ok(nx,ny)) continue;
dis[nx][ny]=t;
vis[nx][ny]=1;
q.pb({nx,ny});
}
}
//for (auto u:q) cout<<u.F<<' '<<u.S<<" ";
//cout<<endl;
if (vis[ex][ey]) break;
for (int i=0;i<n+2;i++) for (int j=0;j<m+2;j++) p[i][j]=0;
for (int i=0;i<q.size();i++){
int x=q[i].F,y=q[i].S;
p[max(1,x-k)][max(1,y-k)]++;
p[max(1,x-k)][min(m,y+k)+1]--;
p[min(n,x+k)+1][max(1,y-k)]--;
p[min(n,x+k)+1][min(m,y+k)+1]--;
if (x-k>=1 && y-k>=1){
p[x-k][y-k]--;
p[x-k+1][y-k]++;
p[x-k][y-k+1]++;
p[x-k+1][y-k+1]--;
}
if (x-k>=1 && y+k<=m){
p[x-k][y+k]--;
p[x-k+1][y+k]++;
p[x-k][y+k+1]++;
p[x-k+1][y+k+1]--;
}
if (x+k<=n && y-k>=1){
p[x+k][y-k]--;
p[x+k+1][y-k]++;
p[x+k][y-k+1]++;
p[x+k+1][y-k+1]--;
}
if (x+k<=n && y+k<=m){
p[x+k][y+k]--;
p[x+k+1][y+k]++;
p[x+k][y+k+1]++;
p[x+k+1][y+k+1]--;
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
if (p[i][j]>0 && !vis[i][j]) q.pb({i,j}),vis[i][j]=1;
//cout<<p[i][j]<<' ';
}//cout<<endl;
}//cout<<endl;
}
}
cout<<dis[ex][ey]<<endl;
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int32_t main()':
Main.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=0;i<q.size();i++){
| ~^~~~~~~~~
Main.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i=0;i<q.size();i++){
| ~^~~~~~~~~
# | 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... |