Submission #1153613

#TimeUsernameProblemLanguageResultExecution timeMemory
1153613vladiliusMaze (JOI23_ho_t3)C++20
51 / 100
2097 ms208848 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int r, c, n, sx, sy, ex, ey; cin>>r>>c>>n>>sx>>sy>>ex>>ey; vector<vector<char>> a(r + 1, vector<char>(c + 1)); vector<vector<vector<pii>>> adj(r + 1, vector<vector<pii>>(c + 1)); set<int> st[r + 1]; for (int i = 1; i <= r; i++){ for (int j = 1; j <= c; j++){ cin>>a[i][j]; if (i > 1) adj[i][j].pb({i - 1, j}); if (j > 1) adj[i][j].pb({i, j - 1}); if (i < r) adj[i][j].pb({i + 1, j}); if (j < c) adj[i][j].pb({i, j + 1}); st[i].insert(j); } } vector<vector<int>> dist(r + 1, vector<int>(c + 1, 1e9)); queue<pii> q, q1; q.push({sx, sy}); dist[sx][sy] = 0; st[sx].erase(sy); auto move = [&](int x, int y){ if (a[x][y] == '.') q1.push({x, y}); for (auto [x1, y1]: adj[x][y]){ if (a[x1][y1] == '.'){ if (dist[x1][y1] == 1e9){ dist[x1][y1] = dist[x][y]; st[x1].erase(y1); q.push({x1, y1}); } q1.push({x1, y1}); } } while (!q1.empty()){ auto [x1, y1] = q1.front(); q1.pop(); for (auto [x2, y2]: adj[x1][y1]){ if (a[x2][y2] == '.' && dist[x2][y2] == 1e9){ dist[x2][y2] = dist[x][y]; st[x2].erase(y2); q.push({x2, y2}); q1.push({x2, y2}); } } } }; move(sx, sy); while (!q.empty()){ auto [x, y] = q.front(); q.pop(); if (x == ex && y == ey){ cout<<dist[x][y]<<"\n"; return 0; } int L = y - n, R = y + n; for (int i = max(1, x - n); i <= min(r, x + n); i++){ int L1 = L + (abs(i - x) == n), R1 = R - (abs(i - x) == n); while (true){ auto it = st[i].lower_bound(L1); if (it == st[i].end() || (*it) > R1) break; int y1 = *it; dist[i][y1] = dist[x][y] + 1; q.push({i, y1}); move(i, y1); st[i].erase(it); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...