This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
void __print(int x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << "'" << x << "'"; }
void __print(const char *x) { cerr << '"' << x << '"'; }
void __print(const string &x) { cerr << '"' << x << '"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ", ";
__print(x.second);
cerr << '}';
}
template <typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? ", " : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v)) cerr << ", ";
_print(v...);
}
#ifdef LOCAL
#define debug(x...) \
cerr << "[" << #x << "] = ["; \
_print(x)
#else
#define debug(x...)
#endif
typedef pair<int, int> T;
const int oo = 1e9 + 7;
const int mx = 2500;
void solve()
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
T s, e;
scanf("%d %d", &s.first, &s.second);
scanf("%d %d", &e.first, &e.second);
vector a(n + 1, vector<char>(m + 1));
function<char()> daj = [&]() {
char c = getchar_unlocked();
if (c == ' ' || c == '\n')
return (char)getchar_unlocked();
return c;
};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = daj();
auto in = [&](T ss) {
return ss.first >= 1 && ss.second >= 1 && ss.first <= n && ss.second <= m;
};
queue<T> q, q2;
vector<bitset<mx>> tab(m + 1);
for (int j = 1; j <= m; j++)
tab[j].set();
const vector<int> X = {-1, 1, 0, 0};
const vector<int> Y = {0, 0, -1, 1};
vector dist(n + 1, vector<int>(m + 1, oo));
dist[s.first][s.second] = 0;
q.push(s);
tab[s.second].set(s.first, 0);
while (dist[e.first][e.second] == oo) {
while ((int)q.size()) {
auto v = q.front();
q.pop();
for (int ck = 0; ck < 4; ck++) {
T x = {v.first + X[ck], v.second + Y[ck]};
if (!in(x)) continue;
if (a[x.first][x.second] == '.') {
if (dist[x.first][x.second] == oo) {
dist[x.first][x.second] = dist[v.first][v.second];
tab[x.second].set(x.first, 0);
q.push(x);
}
}
}
q2.push(v);
}
auto v = q2.front();
q2.pop();
int f = max(1, v.second - k);
int t = min(m, v.second + k);
for (int i = f; i <= t; i++) {
int from = (i == v.second - k || i == v.second + k ? max(1, v.first - k + 1) : max(1, v.first - k));
int to = (i == v.second - k || i == v.second + k ? min(n, v.first + k - 1) : min(n, v.first + k));
for (int now = tab[i]._Find_next(from - 1); now <= to; now = tab[i]._Find_next(now)) {
dist[now][i] = dist[v.first][v.second] + 1;
tab[i].set(now, 0);
q.push({now, i});
}
}
}
printf("%d\n", dist[e.first][e.second]);
}
int32_t main()
{
solve();
}
Compilation message (stderr)
Main.cpp: In function 'void solve()':
Main.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d %d", &s.first, &s.second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d", &e.first, &e.second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |