| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1215440 | stefanneagu | Maze (JOI23_ho_t3) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
deque<pair<int, int>> dq;
vector<vector<int>> mat, rasp;
vector<vector<bool>> f;
int n, m, k;
int si, ei, sj, ej;
bool in(int a, int b) {
return (min({a, b, n - a, m - b}) > 0);
}
void ff(int a, int b, int val) {
if (!in(a, b) || mat[a][b] || f[a][b]) {
return;
}
f[a][b] = 1;
rasp[a][b] = min(rasp[a][b], val);
dq.push_front({a, b});
ff(a + 1, b, val), ff(a, b + 1, val), ff(a - 1, b, val), ff(a, b - 1, val);
}
bool in_timbra(int i, int j) {
int i1 = i - k, j1 = j - k;
int i2 = i + k, j2 = j + k;
if ((ei == i1 && ej == j1) || (ei == i2 && ej == j1) || (ei == i1 && ej == j2) || (ei == i2 && ej == j2)) {
return 0;
}
if (i1 <= ei && ei <= i2 && j1 <= ej && ej <= j2) {
return 1;
}
return 0;
}
int32_t main() {
cin >> n >> m >> k >> si >> sj >> ei >> ej;
rasp.resize(n + 1, vector<int>(m + 1, inf));
mat.resize(n + 1, vector<int>(m + 1, 0));
f.resize(n + 1, vector<bool>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
mat[i][j] = (ch == '.' ? 0 : 1);
}
}
dq.push_front({si, sj});
f[si][sj] = 1;
rasp[si][sj] = 0;
int ans = inf;
while (!dq.empty()) {
auto [i, j] = dq.front();
dq.pop_front();
ff(i + 1, j, rasp[i][j]), ff(i - 1, j, rasp[i][j]), ff(i, j + 1, rasp[i][j]), ff(i, j - 1, rasp[i][j]);
if (in_timbra(i, j)) {
ans = min(ans, rasp[i][j] + 1);
}
// lat sus
for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) {
if (rasp[max(1, i - k)][j2] > rasp[i][j] + 1) {
rasp[max(1, i - k)][j2] = rasp[i][j] + 1;
dq.push_back({max(1, i - k), j2});
}
}
// lat dreapta
for (int i2 = max(1, i - k + 1); i2 <= min(n, j + k - 1); i2++) {
if (rasp[i2][min(m, j + k)] > rasp[i][j] + 1) {
rasp[i2][min(m, j + k)] = rasp[i][j] + 1;
dq.push_back({i2, min(m, j + k)});
}
}
// lat jos
for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) {
if (rasp[min(n, i + k)][j2] > rasp[i][j] + 1) {
rasp[min(n, i + k)][j2] = rasp[i][j] + 1;
dq.push_back({min(n, i + k), j2});
}
}
// lat stanga
for (int i2 = max(1, i - k + 1); i2 <= min(n, j + k - 1); i2++) {
if (rasp[i2][max(1, j - k)] > rasp[i][j] + 1) {
rasp[i2][max(1, j - k)] = rasp[i][j] + 1;
dq.push_back({i2, max(1, j - k)});
}
}
}
cout << min(ans, rasp[ans]);
return 0;
}