Submission #1263544

#TimeUsernameProblemLanguageResultExecution timeMemory
1263544kustov_vadim_533Maze (JOI23_ho_t3)C++20
62 / 100
2093 ms14840 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(); for (int i = max(v.first - n, 0); i < min(v.first + n + 1, r); ++i){ for (int j = max(v.second - n, 0); j < min(v.second + n + 1, c); ++j){ if (abs(i - v.first) + abs(j - v.second) >= 2 * n) continue; if (!us[i][j]){ q1.push({i, j}); us[i][j] = true; } } } } } } 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...