#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 2e7 + 4e6 + 6;
int leaf[2][mn], n, m;
const int dr[4] = {-1, 0, 0, 1};
const int dc[4] = {0, -1, 1, 0};
void build (int layer, int k, int l, int r) {
if (l == r)
return leaf[layer][k] = l, void();
int mid = (l + r) >> 1;
build(layer, 2 * k, l, mid);
build(layer, 2 * k + 1, mid + 1, r);
}
void getNode (int k, int l, int r, int a, int b, vector<int> &vec) {
if (b < l || r < a) return;
if (a <= l && r <= b)
return vec.push_back(k), void();
int mid = (l + r) >> 1;
getNode(2 * k, l, mid, a, b, vec);
getNode(2 * k + 1, mid + 1, r, a, b, vec);
}
int distance (int i, int j, int u, int v) {
return max(abs(i - u), abs(j - v));
}
bool ok (int i, int j) {
if (i < 1 || j < 1) return 0;
if (i > n || j > m) return 0;
return 1;
}
int getInt() {
int num = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
num = (num << 3) + (num << 1) + (ch - '0');
ch = getchar();
}
return num;
}
int main()
{
n = getInt(), m = getInt();
int k = getInt();
int stx = getInt(), sty = getInt(), enx = getInt(), eny = getInt();
vector<vector<bool>> block(n + 1, vector<bool>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c = getchar();
if (c == '#') block[i][j] = 1;
}
}
build(0, 1, 1, n);
build(1, 1, 1, m);
vector<vector<vector<int>>> dist(3);
dist[1] = vector<vector<int>>(4 * n, vector<int>(m + 1, INT_MAX));
dist[2] = vector<vector<int>>(n + 1, vector<int>(4 * m, INT_MAX));
dist[0] = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MAX));
vector<vector<vector<bool>>> vis(3);
vis[1] = vector<vector<bool>>(4 * n, vector<bool>(m + 1));
vis[2] = vector<vector<bool>>(n + 1, vector<bool>(4 * m));
vis[0] = vector<vector<bool>>(n + 1, vector<bool>(m + 1));
deque<tt> q; q.emplace_back(0, stx, sty);
dist[0][stx][sty] = 0;
while (q.size()) {
int layer, x, y; tie(layer, x, y) = q.front(); q.pop_front();
if (vis[layer][x][y]) continue;
vis[layer][x][y] = 1;
function<void(int,int,int,int)> addEdge = [&] (int nlay, int nx, int ny, int w) {
if (dist[layer][x][y] + w >= dist[nlay][nx][ny]) return;
dist[nlay][nx][ny] = dist[layer][x][y] + w;
if (w) q.emplace_back(nlay, nx, ny);
else q.emplace_front(nlay, nx, ny);
};
if (layer == 0) {
if (block[x][y]) {
if (distance(x, y, enx, eny) < k)
return printf("%d", dist[layer][x][y]), 0;
vector<int> nodeX, nodeY;
int xL = max(1, x - k), xR = min(n, x + k), yL = max(1, y - k), yR = min(m, y + k);
getNode(1, 1, n, max(1, x - k + 1), min(n, x + k - 1), nodeX);
getNode(1, 1, m, max(1, y - k + 1), min(m, y + k - 1), nodeY);
for (int u : nodeX) {
addEdge(1, u, yL, 0);
addEdge(1, u, yR, 0);
}
for (int v : nodeY) {
addEdge(2, xL, v, 0);
addEdge(2, xR, v, 0);
}
}
else {
if (distance(x, y, enx, eny) == 0)
return printf("%d", dist[layer][x][y]), 0;
for (int k = 0; k < 4; k++)
if (ok(x + dr[k], y + dc[k]))
addEdge(0, x + dr[k], y + dc[k], block[x + dr[k]][y + dc[k]]);
}
}
else if (layer == 1) {
if (leaf[0][x]) addEdge(0, leaf[0][x], y, block[leaf[0][x]][y]);
else {
addEdge(1, 2 * x, y, 0);
addEdge(1, 2 * x + 1, y, 0);
}
}
else if (layer == 2) {
if (leaf[1][y]) addEdge(0, x, leaf[1][y], block[x][leaf[1][y]]);
else {
addEdge(2, x, 2 * y, 0);
addEdge(2, x, 2 * y + 1, 0);
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
508 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
