Submission #1263549

#TimeUsernameProblemLanguageResultExecution timeMemory
1263549kustov_vadim_533Maze (JOI23_ho_t3)C++20
67 / 100
2095 ms14292 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define len(v) (int)((v).size()) template<typename T> ostream& operator<<(ostream& out, const vector<T> &a){ for (auto& x : a){ out << x << ' '; } out << '\n'; return out; } template<typename T> istream& operator>>(istream& in, vector<T> &a){ for (size_t i = 0; i < a.size(); ++i){ in >> a[i]; } return in; } mt19937 gen; int di[4] = {0, 0, -1, 1}; int dj[4] = {-1, 1, 0, 0}; inline void solve() { int r, c, n; cin >> r >> c >> n; int sr, sc, gr, gc; cin >> sr >> sc >> gr >> gc; --sr, --sc, --gr, --gc; vector<vector<char>> a(r, vector<char>(c)); for (int i = 0; i < r; ++i){ for (int j = 0; j < c; ++j){ cin >> a[i][j]; } } vector<vector<bool>> us(r, vector<bool>(c, false)); queue<pair<int, int>> q1, q2; us[sr][sc] = true; q1.push({sr, sc}); int ans = 0; while (true){ while (!q1.empty()){ pair<int, int> v = q1.front(); q2.push(v); q1.pop(); for (int w = 0; w < 4; ++w){ int ui = v.first + di[w]; int uj = v.second + dj[w]; if (ui < 0 || ui >= r || uj < 0 || uj >= c || a[ui][uj] == '#' || us[ui][uj]) continue; us[ui][uj] = true; q1.push({ui, uj}); } } if (us[gr][gc]){ cout << ans << '\n'; break; } ++ans; while (!q2.empty()){ pair<int, int> v = q2.front(); q2.pop(); if (abs(v.first - gr) <= n && abs(v.second - gc) <= n && abs(v.first - gr) + abs(v.second - gc) <= 2 * n - 1){ us[gr][gc] = true; } int il = max(v.first - n, 0); int ir = min(v.first + n, r - 1); int jl = max(v.second - n, 0); int jr = min(v.second + n, c - 1); for (int i = il; i <= ir; ++i){ bool fl = (i == il || i == ir); for (int j = jl; j <= jr;){ if (!us[i][j] && abs(i - v.first) + abs(j - v.second) < 2 * n){ q1.push({i, j}); us[i][j] = true; } if (fl){ ++j; } else{ j += jr - jl; } } } } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.precision(60); int t = 1; // cin >> t; while (t--) { solve(); } }
#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...