#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int DX[] = {-1, 0, 1, 0};
const int DY[] = {0, 1, 0, -1};
const int oo = 27081993;
int r, c;
string a[2525];
int isValid(int x, int y)
{
return 0 <= x && x < r && 0 <= y && y < c;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, sx, sy, tx, ty;
cin >> r >> c >> n;
cin >> sx >> sy >> tx >> ty;
sx--; sy--; tx--; ty--;
for (int i = 0; i < r; i++)
cin >> a[i];
vector<set<int>> rows(r);
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
rows[i].insert(j);
deque<pair<int, int>> q;
vector<vector<int>> dist(r, vector<int>(c, oo));
vector<vector<int>> isBorder(r, vector<int>(c));
dist[sx][sy] = 0;
isBorder[sx][sy] = 1;
q.push_back({sx, sy});
rows[sx].erase(sy);
while (!empty(q))
{
auto [x, y] = q.front();
q.pop_front();
if (x == tx && y == ty)
{
cout << dist[x][y] << endl;
return 0;
}
for (int i = 0; i < 4; i++)
{
int xx = x + DX[i], yy = y + DY[i];
if (isValid(xx, yy) && a[xx][yy] == '.' && dist[x][y] < dist[xx][yy])
{
dist[xx][yy] = dist[x][y];
isBorder[xx][yy] = 1;
q.push_front({xx, yy});
rows[xx].erase(yy);
}
}
if (!isBorder[x][y])
continue;
for (int xx = max(x - n, 0); xx <= min(x + n, r - 1); xx++)
{
int minY = y - n, maxY = y + n;
if (abs(xx - x) == n)
{
minY++;
maxY--;
}
auto yy = rows[xx].lower_bound(minY);
while (yy != end(rows[xx]))
{
if (*yy > maxY)
break;
dist[xx][*yy] = dist[x][y] + 1;
if (abs(xx - x) == n || abs(*yy - y) == n)
isBorder[xx][*yy] = 1;
q.push_back({xx, *yy});
yy = rows[xx].erase(yy);
}
}
}
assert(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... |