#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct str {
int a, b, c;
const bool operator < (str ult) const {
return a < ult.a;
}
};
priority_queue<str> dq;
vector<vector<int>> rasp;
vector<vector<bool>> mat;
int n, m, k;
int si, ei, sj, ej;
bool in(int a, int b) {
return (min({a, b, n - a + 1, m - b + 1}) > 0);
}
bool in_timbra(int i, int j) {
if ((ei == i - k && ej == j - k) || (ei == i + k && ej == j - k) || (ei == i - k && ej == j + k) || (ei == i + k && ej == j + k)) {
return 0;
}
if (i - k <= ei && ei <= i + k && j - k <= ej && ej <= j + k) {
return 1;
}
return 0;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> k >> si >> sj >> ei >> ej;
rasp.resize(n + 1, vector<int>(m + 1, inf));
mat.resize(n + 1, vector<bool>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
mat[i][j] = (ch == '.' ? 0 : 1);
}
}
dq.push({0, si, sj});
rasp[si][sj] = 0;
int ans = inf;
while (!dq.empty()) {
auto [val, i, j] = dq.top();
dq.pop();
for (int D = 0; D < 4; D++) {
if (in(i + dx[D], j + dy[D]) && !mat[i + dx[D]][j + dy[D]] && rasp[i + dx[D]][j + dy[D]] > rasp[i][j]) {
rasp[i + dx[D]][j + dy[D]] = rasp[i][j];
dq.push({val, i + dx[D], j + dy[D]});
}
}
if (in_timbra(i, j)) {
ans = min(ans, rasp[i][j] + 1);
}
// lat sus
for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) {
if (rasp[max(1, i - k)][j2] > rasp[i][j] + 1) {
rasp[max(1, i - k)][j2] = rasp[i][j] + 1;
dq.push({val + 1, max(1, i - k), j2});
}
}
// lat dreapta
for (int i2 = max(1, i - k + 1); i2 <= min(n, i + k - 1); i2++) {
if (rasp[i2][min(m, j + k)] > rasp[i][j] + 1) {
rasp[i2][min(m, j + k)] = rasp[i][j] + 1;
dq.push({val + 1, i2, min(m, j + k)});
}
}
// lat jos
for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) {
if (rasp[min(n, i + k)][j2] > rasp[i][j] + 1) {
rasp[min(n, i + k)][j2] = rasp[i][j] + 1;
dq.push({val + 1, min(n, i + k), j2});
}
}
// lat stanga
for (int i2 = max(1, i - k + 1); i2 <= min(n, i + k - 1); i2++) {
if (rasp[i2][max(1, j - k)] > rasp[i][j] + 1) {
rasp[i2][max(1, j - k)] = rasp[i][j] + 1;
dq.push({val + 1, i2, max(1, j - k)});
}
}
}
cout << min(ans, rasp[ei][ej]);
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... |