#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
const int INF = 1e9;
const int dx[4] = {-1, 0, +1, 0};
const int dy[4] = {0, -1, 0, +1};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n, m, k;
std::cin >> n >> m >> k;
int x1, y1, x2, y2;
std::cin >> x1 >> y1 >> x2 >> y2;
x1--, y1--, x2--, y2--;
std::vector<std::vector<int>> a(n, std::vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
std::cin >> c;
if (c == '.') {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
std::vector<std::set<std::pair<int, int>>> thisDistance(n * m + 2);
std::vector<std::vector<int>> dist(n, std::vector<int>(m, +INF));
dist[x1][y1] = 0;
thisDistance[0].insert({x1, y1});
for (int d = 0; d <= n * m; d++) {
std::set<std::pair<int, int>> st;
auto dfs = [&](auto &&self, int x, int y) -> void {
st.insert({x, y});
for (int dir = 0; dir < 4; dir++) {
int xx = x + dx[dir], yy = y + dy[dir];
if (0 <= xx && xx < n && 0 <= yy && yy < m && dist[xx][yy] > d && !a[xx][yy]) {
dist[xx][yy] = d;
self(self, xx, yy);
}
}
};
for (const auto &[x, y] : thisDistance[d]) {
if (dist[x][y] < d) {
continue;
}
dfs(dfs, x, y);
st.insert({x, y});
}
for (const auto &[x, y] : st) {
for (int i = std::max(0, x - k); i <= std::min(n - 1, x + k); i++) {
for (int j = std::max(0, y - k); j <= std::min(m - 1, y + k); j++) {
if (dist[i][j] == +INF && std::abs(i - x) + std::abs(j - y) < 2 * k) {
dist[i][j] = d + 1;
thisDistance[d + 1].insert({i, j});
}
}
}
}
}
std::cout << dist[x2][y2];
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... |