#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 6000005, LAYER = 8;
const pii D[4] = {mp(1, 0), mp(-1, 0), mp(0, 1), mp(0, -1)};
int R, C, N;
pii sr, to;
vector<string> s;
int K;
vector<int> edge[MXN * LAYER];
int dis[MXN * LAYER];
inline int cvt(pii p) {
return p.fs * C + p.sc;
}
inline pii cvt(int x) {
return mp(x / C, x % C);
}
inline pii operator+(pii a, pii b) {
return mp(a.fs + b.fs, a.sc + b.sc);
}
inline bool OUT(pii p) {
if (!(0 <= p.fs && p.fs < R)) return true;
if (!(0 <= p.sc && p.sc < C)) return true;
return false;
}
namespace EDGE {
inline int cvt3(int l, int x, int y) {
return l * R * C + x * C + y;
}
inline int PUSH_EDGE(int sr, int to, int val) {
// debug(sr, to, val);
edge[sr].push_back(val ? ~to : to);
}
void E0() {
FOR(i, 0, R * C) {
pii p = cvt(i);
if (s[p.fs][p.sc] == '#') continue;
FOR(d, 0, 4) {
pii nxt = p + D[d];
if (OUT(nxt)) continue;
if (s[nxt.fs][nxt.sc] == '#') continue;
PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
}
}
}
void E0_1() {
FOR(i, 0, R * C) {
pii p = cvt(i);
FOR(d, 0, 4) {
pii nxt = p + D[d];
if (OUT(nxt)) continue;
PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(1, nxt.fs, nxt.sc), 1);
}
}
}
void E23_4() {
FOR(j, 0, C) {
for (int l_bnd = 0, r_bnd; l_bnd < R; l_bnd += K) {
r_bnd = min(R, l_bnd + K);
FOR(i, l_bnd, r_bnd) {
PUSH_EDGE(cvt3(2, i, j), cvt3(4, i, j), 0);
PUSH_EDGE(cvt3(3, i, j), cvt3(4, i, j), 0);
}
FOR(i, l_bnd, r_bnd - 1) PUSH_EDGE(cvt3(2, i, j), cvt3(2, i + 1, j), 0);
FOR(i, l_bnd + 1, r_bnd) PUSH_EDGE(cvt3(3, i, j), cvt3(3, i - 1, j), 0);
}
}
}
void E1_23() {
auto ADD_EDGE = [&](int y, int l, int r, int sr) -> void {
if (r - l == K) {
PUSH_EDGE(sr, cvt3(2, l, y), 0);
PUSH_EDGE(sr, cvt3(3, r - 1, y), 0);
return;
}
if (r == R) {
PUSH_EDGE(sr, cvt3(2, l, y), 0);
int m = (l ? (l - 1) / K * K + K : 0);
if (m < R) PUSH_EDGE(sr, cvt3(2, m, y), 0);
return;
}
PUSH_EDGE(sr, cvt3(3, r - 1, y), 0);
};
FOR(j, 0, C) {
FOR(i, 0, R) {
int l_bnd = max(0, i - (N - 1)), r_bnd = min(R, i + N);
ADD_EDGE(j, l_bnd, r_bnd, cvt3(1, i, j));
}
}
}
void E56_7() {
FOR(i, 0, R) {
for (int l_bnd = 0, r_bnd; l_bnd < C; l_bnd += K) {
r_bnd = min(C, l_bnd + K);
FOR(j, l_bnd, r_bnd) {
PUSH_EDGE(cvt3(5, i, j), cvt3(7, i, j), 0);
PUSH_EDGE(cvt3(6, i, j), cvt3(7, i, j), 0);
}
FOR(j, l_bnd, r_bnd - 1) PUSH_EDGE(cvt3(5, i, j), cvt3(5, i, j + 1), 0);
FOR(j, l_bnd + 1, r_bnd) PUSH_EDGE(cvt3(6, i, j), cvt3(6, i, j - 1), 0);
}
}
}
void E4_56() {
auto ADD_EDGE = [&](int x, int l, int r, int sr) -> void {
if (r - l == K) {
PUSH_EDGE(sr, cvt3(5, x, l), 0);
PUSH_EDGE(sr, cvt3(6, x, r - 1), 0);
return;
}
if (r == C) {
PUSH_EDGE(sr, cvt3(5, x, l), 0);
int m = (l ? (l - 1) / K * K + K : 0);
if (m < C) PUSH_EDGE(sr, cvt3(5, x, m), 0);
return;
}
PUSH_EDGE(sr, cvt3(6, x, r - 1), 0);
};
FOR(i, 0, R) {
FOR(j, 0, C) {
int l_bnd = max(0, j - (N - 1)), r_bnd = min(C, j + N);
ADD_EDGE(i, l_bnd, r_bnd, cvt3(4, i, j));
}
}
}
void E7_0() {
FOR(i, 0, R * C) {
pii p = cvt(i);
FOR(d, 0, 4) {
pii nxt = p + D[d];
if (OUT(nxt) || s[nxt.fs][nxt.sc] == '#') continue;
PUSH_EDGE(cvt3(7, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
}
}
}
void BUILD() {
E0();
E0_1();
E23_4();
E1_23();
E56_7();
E4_56();
E7_0();
}
}
namespace BFS {
deque<pii> dq;
void GO(int sr) {
fill(dis, dis + R * C * LAYER, -1);
dq.push_back(mp(0, sr));
while (dq.size()) {
pii now = dq.front();
dq.pop_front();
// debug(now.fs, now.sc);
if (dis[now.sc] != -1) continue;
int len = now.fs, id = now.sc;
dis[id] = len;
for (auto &i : edge[id]) {
int tg = (i < 0 ? ~i : i);
if (dis[tg] != -1) continue;
if (i < 0) dq.push_back(mp(len + 1, tg));
else dq.push_front(mp(len, tg));
}
}
}
}
void miku() {
cin >> R >> C >> N >> sr.fs >> sr.sc >> to.fs >> to.sc;
sr.fs--, sr.sc--, to.fs--, to.sc--;
K = N * 2 - 1;
s.resize(R);
FOR(i, 0, R) cin >> s[i];
EDGE::BUILD();
BFS::GO(cvt(sr));
cout << dis[cvt(to)] << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(iostream::failbit);
miku();
return 0;
}
Compilation message
Main.cpp: In function 'int EDGE::PUSH_EDGE(int, int, int)':
Main.cpp:55:5: warning: no return statement in function returning non-void [-Wreturn-type]
55 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
734 ms |
1463708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
598 ms |
1463892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
722 ms |
1463708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
598 ms |
1463892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
598 ms |
1463892 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
734 ms |
1463708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
734 ms |
1463708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
734 ms |
1463708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
