#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int r, c, n, sx, sy, ex, ey; cin>>r>>c>>n>>sx>>sy>>ex>>ey;
vector<vector<char>> a(r + 1, vector<char>(c + 1));
vector<vector<vector<pii>>> adj(r + 1, vector<vector<pii>>(c + 1));
set<int> st[r + 1];
for (int i = 1; i <= r; i++){
for (int j = 1; j <= c; j++){
cin>>a[i][j];
if (i > 1) adj[i][j].pb({i - 1, j});
if (j > 1) adj[i][j].pb({i, j - 1});
if (i < r) adj[i][j].pb({i + 1, j});
if (j < c) adj[i][j].pb({i, j + 1});
st[i].insert(j);
}
}
vector<vector<int>> dist(r + 1, vector<int>(c + 1, 1e9));
queue<pii> q1, q2;
queue<pii> q[r * c + 1]; q[0].push({sx, sy});
dist[sx][sy] = 0; st[sx].erase(sy);
auto move = [&](int x, int y){
if (a[x][y] == '.') q1.push({x, y});
for (auto [x1, y1]: adj[x][y]){
if (a[x1][y1] == '.'){
if (dist[x1][y1] == 1e9){
dist[x1][y1] = dist[x][y];
st[x1].erase(y1);
q[dist[x1][y1]].push({x1, y1});
}
q1.push({x1, y1});
}
}
while (!q1.empty()){
auto [x1, y1] = q1.front(); q1.pop();
for (auto [x2, y2]: adj[x1][y1]){
if (a[x2][y2] == '.' && dist[x2][y2] == 1e9){
dist[x2][y2] = dist[x][y];
st[x2].erase(y2);
q[dist[x2][y2]].push({x2, y2});
q1.push({x2, y2});
}
}
}
};
for (int i = 0; i <= r * c; i++){
while (!q[i].empty()){
auto [x, y] = q[i].front(); q[i].pop();
move(x, y);
if (x == ex && y == ey){
cout<<dist[x][y]<<"\n";
return 0;
}
int L = y - n, R = y + n;
q2.push({x, y});
while (!q2.empty()){
auto [x1, y1] = q2.front(); q2.pop();
int L1 = L + (abs(x1 - x) == n), R1 = R - (abs(x1 - x) == n);
if (!(abs(x1 - x) <= n && L1 <= y1 && y1 <= R1)){
continue;
}
if (dist[x1][y1] == 1e9){
dist[x1][y1] = dist[x][y] + 1;
q[dist[x1][y1]].push({x1, y1});
st[x1].erase(y1);
}
for (auto [x2, y2]: adj[x1][y1]){
if (dist[x2][y2] > dist[x1][y1]){
q2.push({x2, y2});
}
}
}
}
}
}
# | 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... |