제출 #1153665

#제출 시각아이디문제언어결과실행 시간메모리
1153665vladiliusMaze (JOI23_ho_t3)C++20
8 / 100
1941 ms1212840 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> q1, q2; queue<pii> q[r * c + 1]; q[0].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[dist[x1][y1]].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[dist[x2][y2]].push({x2, y2}); q1.push({x2, y2}); } } } }; for (int i = 0; i <= r * c; i++){ while (!q[i].empty()){ auto [x, y] = q[i].front(); q[i].pop(); move(x, y); if (x == ex && y == ey){ cout<<dist[x][y]<<"\n"; return 0; } int L = y - n, R = y + n; q2.push({x, y}); while (!q2.empty()){ auto [x1, y1] = q2.front(); q2.pop(); int L1 = L + (abs(x1 - x) == n), R1 = R - (abs(x1 - x) == n); if (!(abs(x1 - x) <= n && L1 <= y1 && y1 <= R1)){ continue; } if (dist[x1][y1] == 1e9){ dist[x1][y1] = dist[x][y] + 1; q[dist[x1][y1]].push({x1, y1}); st[x1].erase(y1); } for (auto [x2, y2]: adj[x1][y1]){ if (dist[x2][y2] > dist[x1][y1]){ q2.push({x2, y2}); } } } } } }
#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...