#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
const int INF = 1e9;
const int dx[4] = {-1, 0, +1, 0};
const int dy[4] = {0, -1, 0, +1};
struct Fenwick2D {
std::vector<std::vector<int>> aib;
int n, m;
void init(int _n, int _m) {
n = _n + 2;
m = _m + 2;
aib = std::vector<std::vector<int>>(n + 3, std::vector<int>(m + 3, 0));
}
void update(int x, int y, int v) {
x++, y++;
for (int i = x; i < n; i += i & -i) {
for (int j = y; j < m; j += j & -j) {
aib[i][j] += v;
}
}
}
int query(int x, int y) {
x++, y++;
int ret = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
ret += aib[i][j];
}
}
return ret;
}
int pointQuery(int i, int j) {
return query(i, j) - query(i, j - 1) - query(i - 1, j) + query(i - 1, j - 1);
}
int querySubmatrix(int x1, int y1, int x2, int y2) {
return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
std::vector<std::pair<int, int>> findAll(int x1, int y1, int x2, int y2) {
x1++, y1++, x2++, y2++;
std::vector<std::pair<int, int>> ret;
int i = x1;
while (querySubmatrix(i - 1, y1 - 1, x2 - 1, y2 - 1)) {
int l = i, r = x2;
while (l < r) {
int mid = (l + r) / 2;
if (querySubmatrix(i - 1, y1 - 1, mid - 1, y2 - 1)) {
r = mid;
} else {
l = mid + 1;
}
}
int p = y1;
int steps2 = querySubmatrix(i - 1, y1 - 1, i - 1, y2 - 1);
while (steps2--) {
int l = p, r = y2;
while (l < r) {
int mid = (l + r) / 2;
if (querySubmatrix(i - 1, p - 1, i - 1, mid - 1)) {
r = mid;
} else {
l = mid + 1;
}
}
ret.push_back({i, r});
p = r + 1;
}
i++;
}
return ret;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n, m, k;
std::cin >> n >> m >> k;
int x1, y1, x2, y2;
std::cin >> x1 >> y1 >> x2 >> y2;
x1--, y1--, x2--, y2--;
std::vector<std::vector<int>> a(n, std::vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
std::cin >> c;
if (c == '.') {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
std::vector<std::set<std::pair<int, int>>> thisDistance(n * m + 2);
std::vector<std::vector<int>> dist(n, std::vector<int>(m, +INF));
dist[x1][y1] = 0;
thisDistance[0].insert({x1, y1});
Fenwick2D DS;
DS.init(n, m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
DS.update(i, j, +1);
}
}
auto removeSubmatrix = [&](int x1, int y1, int x2, int y2, int d) {
x1 = std::max(x1, 0);
y1 = std::max(y1, 0);
x2 = std::min(x2, n - 1);
y2 = std::min(y2, m - 1);
if (x1 > x2 || y1 > y2) {
return;
}
auto ret = DS.findAll(x1, y1, x2, y2);
for (auto [x, y] : ret) {
x--, y--;
assert(DS.pointQuery(x, y) == 1);
DS.update(x, y, -1);
dist[x][y] = d + 1;
thisDistance[d + 1].insert({x, y});
}
};
for (int d = 0; d <= n * m; d++) {
std::set<std::pair<int, int>> st;
auto dfs = [&](auto &&self, int x, int y) -> void {
st.insert({x, y});
for (int dir = 0; dir < 4; dir++) {
int xx = x + dx[dir], yy = y + dy[dir];
if (0 <= xx && xx < n && 0 <= yy && yy < m && dist[xx][yy] > d && !a[xx][yy]) {
dist[xx][yy] = d;
self(self, xx, yy);
}
}
};
for (const auto &[x, y] : thisDistance[d]) {
if (dist[x][y] < d) {
continue;
}
dfs(dfs, x, y);
st.insert({x, y});
}
if (st.count({x2, y2})) {
std::cout << d;
return 0;
}
for (const auto &[x, y] : st) {
if (DS.pointQuery(x, y) == 1) {
DS.update(x, y, -1);
}
}
for (const auto &[x, y] : st) {
removeSubmatrix(x - (k - 1), y - k, x + (k - 1), y + k, d);
removeSubmatrix(x - k, y - (k - 1), x - k, y + (k - 1), d);
removeSubmatrix(x + k, y - (k - 1), x + k, y + (k - 1), d);
}
}
std::cout << dist[x2][y2];
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... |