This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct BIT2D
{
int n, m;
vector<vector<int>> bit;
BIT2D(int n_, int m_) : n(n_), m(m_), bit(n + 1, vector<int>(m + 1)) {}
void add(int i_, int j_, int u)
{
for (int i = i_ + 1; i <= n; i += i & -i)
{
for (int j = j_ + 1; j <= m; j += j & -j)
{
bit[i][j] += u;
}
}
}
int query(int i_, int j_)
{
int ret = 0;
for (int i = i_; i > 0; i -= i & -i)
{
for (int j = j_; j > 0; j -= j & -j)
{
ret += bit[i][j];
}
}
return ret;
}
int query(int l1, int r1, int l2, int r2)
{
return query(l1, l2) + query(r1, r2) - query(l1, r2) - query(r1, l2);
}
};
const int C = 80, INF = 1e9 + 10;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n, m, K;
cin >> n >> m >> K;
pair<int, int> A, B;
cin >> A.first >> A.second >> B.first >> B.second;
A.first--, A.second--, B.first--, B.second--;
vector<string> g(n);
for (int i = 0; i < n; i++)
{
cin >> g[i];
}
vector<vector<int>> rgt(n, vector<int>(m, -1));
vector<vector<bool>> vis(n, vector<bool>(m));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m - 1; j++)
{
rgt[i][j] = j + 1;
}
}
auto able = [&](int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < m;
};
function<int(int, int)> rr = [&](int i, int j) -> int
{
if (j == -1 || !vis[i][j])
{
return j;
}
return rgt[i][j] = rr(i, rgt[i][j]);
};
vector<vector<int>> dis(n, vector<int>(m, INF));
if (K < C)
{
vector<pair<int, int>> res;
res.push_back(A);
vis[A.first][A.second] = 1;
dis[A.first][A.second] = 0;
while (res.size())
{
vector<pair<int, int>> res2;
while (res.size())
{
auto [i, j] = res.back();
res2.emplace_back(i, j);
res.pop_back();
for (auto &[dx, dy] : vector<pair<int, int>>{{1, 0}, {0, 1}, {-1, 0}, {0, -1}})
{
if (able(i + dx, j + dy) && !vis[i + dx][j + dy] && g[i + dx][j + dy] == '.')
{
res.emplace_back(i + dx, j + dy);
dis[i + dx][j + dy] = dis[i][j];
vis[i + dx][j + dy] = 1;
if (vis[B.first][B.second])
{
goto found;
}
}
}
}
while (res2.size())
{
auto [i, j] = res2.back();
res2.pop_back();
for (int ii : {max(0, i - K), min(n - 1, i + K)})
{
int jj = rr(ii, max(0, j - (K - 1)));
while (jj != -1 && jj <= j + (K - 1))
{
res.emplace_back(ii, jj);
dis[ii][jj] = dis[i][j] + 1;
vis[ii][jj] = 1;
jj = rr(ii, max(0, j - (K - 1)));
if (vis[B.first][B.second])
{
goto found;
}
}
}
for (int ii = max(0, i - (K - 1)); ii <= min(n - 1, i + (K - 1)); ii++)
{
int jj = rr(ii, max(0, j - K));
while (jj != -1 && jj <= j + K)
{
res.emplace_back(ii, jj);
dis[ii][jj] = dis[i][j] + 1;
vis[ii][jj] = 1;
jj = rr(ii, max(0, j - K));
if (vis[B.first][B.second])
{
goto found;
}
}
}
}
}
}
else
{
BIT2D bit(n, m);
vector<pair<int, int>> res;
res.push_back(A);
vis[A.first][A.second] = 1;
dis[A.first][A.second] = 0;
bit.add(A.first, A.second, 1);
while (res.size())
{
int d = dis[res[0].first][res[0].second];
while (res.size())
{
auto [i, j] = res.back();
res.pop_back();
for (auto &[dx, dy] : vector<pair<int, int>>{{1, 0}, {0, 1}, {-1, 0}, {0, -1}})
{
if (able(i + dx, j + dy) && !vis[i + dx][j + dy] && g[i + dx][j + dy] == '.')
{
res.emplace_back(i + dx, j + dy);
dis[i + dx][j + dy] = dis[i][j];
vis[i + dx][j + dy] = 1;
bit.add(i + dx, j + dy, 1);
if (vis[B.first][B.second])
{
goto found;
}
}
}
}
for (int i = 0; i < n; i++)
{
int j = rr(i, 0);
while (j != -1 && j < m)
{
if (bit.query(max(0, i - K), min(n, i + (K + 1)), max(0, j - K), min(m, j + (K + 1))) \
- int(able(i - K, j - K) && vis[i - K][j - K]) \
- int(able(i - K, j + K) && vis[i - K][j + K]) \
- int(able(i + K, j - K) && vis[i + K][j - K]) \
- int(able(i + K, j + K) && vis[i + K][j + K]) > 0)
{
res.emplace_back(i, j);
}
j = rr(i, j + 1);
}
}
for (auto &[i, j] : res)
{
dis[i][j] = d + 1;
vis[i][j] = 1;
bit.add(i, j, 1);
if (vis[B.first][B.second])
{
goto found;
}
}
}
}
found:
int ans = dis[B.first][B.second];
cout << ans << '\n';
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... |