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 dx[] = {1, 0, -1, 0},
dy[] = {0, 1, 0, -1};
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int r, c, n; cin >> r >> c >> n;
int Sr, Sc; cin >> Sr >> Sc;
int Gr, Gc; cin >> Gr >> Gc;
vector<vector<char>> a(r + 10, vector<char>(c + 10));
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) cin >> a[i][j];
}
vector<vector<pair<int, int>>> ad(2 * r * c + 10);
auto in = [&](int x, int y) { return 1 <= x && x <= r && 1 <= y && y <= r; };
auto idx = [&](int i, int j) { return i * c - c + j; };
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
int u = idx(i, j);
for (int t = 0; t < 4; ++t) {
if (!in(i + dx[t], j + dy[t])) continue;
int v = idx(i + dx[t], j + dy[t]);
if (a[i + dx[t]][j + dy[t]] == '.') ad[u].push_back({v, 0});
}
}
}
int it = idx(r, c);
for (int i = 1; i <= r; ++i) {
for (int j = 1; j <= c; ++j) {
vector<int> foo = {-1, 0, n - 1, n};
it += 1;
for (int t = j; t < min(c, j + n); ++t) {
for (int type = 0; type < 4; ++type) {
if (!in(i + foo[type], t)) continue;
int v = idx(i + foo[type], t);
ad[it].push_back({v, 1});
ad[v].push_back({it, 1});
}
}
for (int t = i; t < min(r, i + n); ++t) {
for (int type = 0; type < 4; ++type) {
if (!in(t, j + foo[type])) continue;
int v = idx(t, j + foo[type]);
ad[it].push_back({v, 1});
ad[v].push_back({it, 1});
}
}
if (i <= Gr && j <= Gc && Gr <= i + n - 1 && Gc <= j + n - 1) {
ad[it].push_back({idx(Gr, Gc), 1});
ad[idx(Gr, Gc)].push_back({it, 1});
}
}
}
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<>> q;
vector<int> f(it, 1'000'000'000);
q.push({f[idx(Sr, Sc)] = 0, idx(Sr, Sc)});
while (q.size()) {
auto [d, u] = q.top(); q.pop();
if (d != f[u]) continue;
for (const auto& [v, w] : ad[u])
if (f[v] > d + w) q.push({f[v] = d + w, v});
}
cout << (f[idx(Gr, Gc)] + 1) / 2 << "\n";
}
# | 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... |