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;
#define pii pair<int, int>
vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int r, c, n; cin >> r >> c >> n;
int sx, sy; cin >> sx >> sy; --sx, --sy;
int gx, gy; cin >> gx >> gy; --gx, --gy;
vector<string> arr(r);
for (int i = 0; i < r; ++i) cin >> arr[i];
// . = empty
// # = wall
vector<vector<bool>> vis(r, vector<bool>(c));
vis[sx][sy] = true;
vector<pii> q; q.push_back({sx, sy});
queue<pii> rq; for (pii _p : q) rq.push(_p);
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (arr[nx][ny] == '#' || vis[nx][ny]) continue;
rq.push({nx, ny});
q.push_back({nx, ny});
vis[nx][ny] = true;
}
}
if (vis[gx][gy]) {
cout << 0 << '\n';
return 0;
}
vector<vector<int>> dists(r, vector<int>(c));
for (int dist = 1;; ++dist) {
if (!q.size()) break;
// cout << "here" << endl;
vector<pii> nq;
queue<pii> rq; for (pii _p : q) rq.push(_p), dists[_p.first][_p.second] = 0;
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = true;
dists[nx][ny] = dists[xx][yy] + 1;
if (dists[nx][ny] < 2 * n - 1) rq.push({nx, ny});
nq.push_back({nx, ny});
}
}
for (pii _p : nq) rq.push(_p);
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
// cout << xx << ' ' << yy << endl;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (arr[nx][ny] == '#' || vis[nx][ny]) continue;
rq.push({nx, ny});
nq.push_back({nx, ny});
vis[nx][ny] = true;
}
}
if (vis[gx][gy]) {
cout << dist << '\n';
return 0;
}
q = nq;
}
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... |