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>
using namespace std;
const int INF = 1e9;
const int maxr = 3001;
const int maxc = 6000001;
set<int> r[maxr];
set<short> c[maxc];
vector<short> vis[maxr];
vector<int> d[maxr];
vector<bool> a[maxr];
deque<pair<int,int>> f;
int R,C,n;
int bfs(int si,int sj,int fi,int fj)
{
for(int i = 0;i < R;++i)
{
d[i].resize(C);
vis[i].resize(C);
for(int j = 0;j < C;++j)
{
d[i][j] = INF;
vis[i][j] = 0;
if(i != si || j != sj)
{
r[i].insert(j);
c[j].insert(i);
}
}
}
d[si][sj] = 0;
vis[si][sj] = 2;
f.push_back({si,sj});
while(f.size())
{
int i = f[0].first;
int j = f[0].second;
f.pop_front();
// cout << i << ' ' << j << ' ' << d[fi][fj] << ' ' << vis[5][0] << "\n";
if(vis[i][j] == 3)
continue;
vis[i][j] = 3;
if(i == fi && j == fj)
break;
if(i > 0 && a[i-1][j] == 0 && vis[i-1][j] < 2)
{
if(!vis[i-1][j])
{
r[i-1].erase(j);
c[j].erase(i-1);
}
vis[i-1][j] = 2;
d[i-1][j] = d[i][j];
f.push_front({i-1,j});
}
if(j > 0 && a[i][j-1] == 0 && vis[i][j-1] < 2)
{
if(!vis[i][j-1])
{
r[i].erase(j-1);
c[j-1].erase(i);
}
// if(i == 5 && j == 1)
// {
// cout << d[i][j] << ' ' << d[i][j-1] << "\n";
// }
vis[i][j-1] = 2;
d[i][j-1] = d[i][j];
f.push_front({i,j-1});
}
if(i < R-1 && a[i+1][j] == 0 && vis[i+1][j] < 2)
{
if(!vis[i+1][j])
{
r[i+1].erase(j);
c[j].erase(i+1);
}
vis[i+1][j] = 2;
d[i+1][j] = d[i][j];
f.push_front({i+1,j});
}
if(j < C-1 && a[i][j+1] == 0 && vis[i][j+1] < 2)
{
if(!vis[i][j+1])
{
r[i].erase(j+1);
c[j+1].erase(i);
}
vis[i][j+1] = 2;
d[i][j+1] = d[i][j];
f.push_front({i,j+1});
}
if(abs(i-fi) <= n && abs(j-fj) <= n && !vis[fi][fj])
{
r[fi].erase(fj);
c[fj].erase(fi);
//cout << i << ' ' << j << ' ' << d[i][j] << "!\n";
vis[fi][fj] = 1;
d[fi][fj] = d[i][j]+1;
f.push_back({fi,fj});
}
short indd = min(R-1,i+n);
short indu = max(0,i-n);
int indl = max(0,j-n);
int indr = min(C-1,j+n);
short indd2 = i+n-1;
short indu2 = i-n+1;
int indr2 = j+n-1;
int indl2 = j-n+1;
for(;;)
{
auto it = r[indd].lower_bound(indl2);
if(it != r[indd].end() && (*it) <= indr2)
{
int k = (*it);
vis[indd][k] = 1;
//cout << indd << ' ' << k << ' ' << d[i][j] << "!\n";
d[indd][k] = d[i][j]+1;
//cout << d[1][0] << ' ';
f.push_back({indd,k});
r[indd].erase(it);
c[(*it)].erase(indd);
}
else
break;
}
for(;;)
{
auto it = r[indu].lower_bound(indl2);
if(it != r[indu].end() && (*it) <= indr2)
{
int k = (*it);
vis[indu][k] = 1;
d[indu][k] = d[i][j]+1;
//cout << indu << ' ' << k << "!!\n";
f.push_back({indu,k});
r[indu].erase(it);
c[(*it)].erase(indu);
}
else
break;
}
for(;;)
{
auto it = c[indl].lower_bound(indu2);
if(it != c[indl].end() && (*it) <= indd2)
{
int k = (*it);
vis[k][indl] = 1;
d[k][indl] = d[i][j]+1;
//cout << k << ' ' << indl << "!!!\n";
f.push_back({k,indl});
c[indl].erase(it);
r[(*it)].erase(indl);
}
else
break;
}
for(;;)
{
auto it = c[indr].lower_bound(indu2);
if(it != c[indr].end() && (*it) <= indd2)
{
int k = (*it);
vis[k][indr] = 1;
d[k][indr] = d[i][j]+1;
//cout << k << ' ' << indr << "!!!!\n";
f.push_back({k,indr});
c[indr].erase(it);
r[(*it)].erase(indr);
}
else
break;
}
}
return d[fi][fj];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> n;
int si,sj,fi,fj;
cin >> si >> sj >> fi >> fj;
si--;
sj--;
fi--;
fj--;
for(int i = 0;i < R;++i)
{
string s;
cin >> s;
a[i].resize(C);
for(int j =0;j < C;++j)
{
a[i][j] = (s[j] == '.' ? 0 : 1);
}
}
cout << bfs(si,sj,fi,fj) << "\n";
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... |