#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;
ll get(ll x, vector<ll>& parent){
if(parent[x] == x) return x;
return parent[x] = get(parent[x], parent);
}
void unite(ll x, ll y, vector<ll>& parent){
x = get(x, parent);
y = get(y, parent);
parent[x] = y;
}
void push(ll pos, ll r, ll c, vector<ll>& dis, queue<ll>& q){
ll x = pos/c, y = pos%c;
if(x < r-1 and dis[pos + c] > dis[pos]){
dis[pos + c] = dis[pos];
q.push(pos + c);
}
if(x > 0 and dis[pos - c] > dis[pos]){
dis[pos - c] = dis[pos];
q.push(pos - c);
}
if(y < c-1 and dis[pos+1] > dis[pos]){
dis[pos+1] = dis[pos];
q.push(pos+1);
}
if(y > 0 and dis[pos-1] > dis[pos]){
dis[pos-1] = dis[pos];
q.push(pos-1);
}
}
void push2(ll pos, ll r, ll c, ll n, vector<ll>& dis, queue<ll>& q, vector<ll>& parent, vector<ll>& parent2){
ll x = pos/c, y = pos%c, curX, curY, nextX, nextY, nextPos, endPos;
curX = max(0ll, x - n);
curY = max(0ll, y - n + 1);
nextY = min(c-1, curY + 2*n - 2);
nextPos = curX*c + curY;
nextPos = get(nextPos, parent);
endPos = curX*c + nextY;
while(true){
if(nextPos >= endPos){
if(dis[endPos] > dis[pos] + 1){
dis[endPos] = dis[pos] + 1;
q.push(endPos);
}
break;
}
if(dis[nextPos] > dis[pos] + 1){
dis[nextPos] = dis[pos] + 1;
q.push(nextPos);
}
unite(nextPos, nextPos+1, parent);
nextPos = get(nextPos, parent);
}
curX = min(r-1, x + n);
nextPos = curX*c + curY;
nextPos = get(nextPos, parent);
endPos = curX*c + nextY;
while(true){
if(nextPos >= endPos){
if(dis[endPos] > dis[pos] + 1){
dis[endPos] = dis[pos] + 1;
q.push(endPos);
}
break;
}
if(dis[nextPos] > dis[pos] + 1){
dis[nextPos] = dis[pos] + 1;
q.push(nextPos);
}
unite(nextPos, nextPos+1, parent);
nextPos = get(nextPos, parent);
}
curX = max(0ll, x - n + 1);
curY = max(0ll, y - n);
nextX = min(r-1, curX + 2*n - 2);
nextPos = curX*c + curY;
nextPos = get(nextPos, parent2);
endPos = nextX*c + curY;
while(true){
if(nextPos >= endPos){
if(dis[endPos] > dis[pos] + 1){
dis[endPos] = dis[pos] + 1;
q.push(endPos);
}
break;
}
if(dis[nextPos] > dis[pos] + 1){
dis[nextPos] = dis[pos] + 1;
q.push(nextPos);
}
unite(nextPos, nextPos+c, parent2);
nextPos = get(nextPos, parent2);
}
curY = min(c-1, y + n);
nextPos = curX*c + curY;
nextPos = get(nextPos, parent2);
endPos = nextX*c + curY;
while(true){
if(nextPos >= endPos){
if(dis[endPos] > dis[pos] + 1){
dis[endPos] = dis[pos] + 1;
q.push(endPos);
}
break;
}
if(dis[nextPos] > dis[pos] + 1){
dis[nextPos] = dis[pos] + 1;
q.push(nextPos);
}
unite(nextPos, nextPos+c, parent2);
nextPos = get(nextPos, parent2);
}
}
void solve(){
ll r, c, n, startR, startC, finishR, finishC, i, j, pos, distance=0;
char x;
cin>>r>>c>>n>>startR>>startC>>finishR>>finishC;
--startR;
--startC;
--finishR;
--finishC;
vector<ll> a(r*c);
vector<ll> dis(r*c, inf);
vector<ll> parent(r*c);
vector<ll> parent2(r*c);
for(i=0;i<r;++i){
for(j=0;j<c;++j){
cin>>x;
a[i*c + j] = x == '.';
parent[i*c + j] = i*c + j;
parent2[i*c + j] = i*c + j;
}
}
queue<ll> q1, q2;
dis[startR*c + startC] = 0;
q1.push(startR*c + startC);
while(!q1.empty()){
while(!q1.empty()){
pos = q1.front();
q1.pop();
if(dis[pos] < distance) continue;
if(a[pos]){
push(pos, r, c, dis, q1);
}else{
push2(pos, r, c, n, dis, q2, parent, parent2);
}
}
++distance;
swap(q1, q2);
}
for(i=max(0ll, finishR-n+1);i<min(r-1, finishR+n-1);++i){
for(j=max(0ll, finishC-n+1);j<min(c-1, finishC+n-1);++j){
dis[finishR*c + finishC] = min(dis[finishR*c + finishC], dis[i*c+j] + 1);
}
}
cout<<dis[finishR*c + finishC]<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
srand(time(nullptr));
ll t=1;
// cin>>t;
for(;t>0;--t){
solve();
}
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... |