| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1123405 | Neco_arc | Maze (JOI23_ho_t3) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define name "Maze"
#define fi(i, a, b) for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (6e6 + 7)
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, m, c;
int stx, sty, fnx, fny;
vector<vector<int>> dist, a;
queue<array<int, 4>> q_good, q_bad;
inline bool inside(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
int BFS() {
dist[stx][sty] = 0;
q_good.push({stx, sty, 0, 0});
while(q_good.size() || q_bad.size()) { /// bad go first to simulate the dijkstra
while(q_bad.size()) {
auto [x, y, sx, sy] = q_bad.front(); q_bad.pop();
if(sx == 0 && sy == 0) q_good.push({x, y, 0, 0});
fi(t, 0, 3) {
int u = x + dx[t], v = y + dy[t];
int rx = sx - abs(dx[t]), ry = sy - abs(dy[t]);
if(rx >= 0 && ry >= 0 && inside(u, v) && dist[u][v] == -1) {
dist[u][v] = dist[x][y];
q_bad.push({u, v, rx, ry});
}
}
}
while(q_good.size()) {
auto [x, y, sx, sy] = q_good.front(); q_good.pop();
fi(t, 0, 3) {
int u = x + dx[t], v = y + dy[t];
if(!inside(u, v) || dist[u][v] != -1) continue;
dist[u][v] = dist[x][y] + a[u][v];
if(a[u][v]) q_bad.push({u, v, c - 1, c - 1});
else q_good.push({u, v, 0, 0});
}
}
}
return dist[fnx][fny];
}
void solve() {
cin >> n >> m >> c;
cin >> stx >> sty >> fnx >> fny;
a.resize(n + 2, vector<int>(m + 2));
dist.resize(n + 2, vector<int>(m + 2, -1));
fi(i, 1, n) fi(j, 1, m) {
char x; cin >> x;
a[i][j] = x == '#';
}
assert(a[stx][sty] == 0);
assert(a[fnx][fny] == 0);
cout << BFS();
}