제출 #1249742

#제출 시각아이디문제언어결과실행 시간메모리
1249742norman165Maze (JOI23_ho_t3)C++20
62 / 100
88 ms30200 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define int long long #define yes() cout << "YES\n" #define no() cout << "NO\n" using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; const int inf = 1e18; const int mod = 1e9 + 7; const int maxn = 1e7 + 5e6; const int mod1 = 998244353; const int mod2 = 1e18 + 1; const int mod3 = 1e9 + 9; const int mod4 = 333333333; const int mod5 = 200000; const int mod6 = 10007; const int k = 300; const int w = 1e5; const ld EPS = 1e-8; int LOG = 30; struct e { int x, y, p, q; }; void solve() { int k, n, m; cin >> n >> m >> k; int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--, y1--, x2--, y2--; vector<vector<int>> d(n, vector<int> (m, inf)); d[x1][y1] = 0; vector<string> a(n); for (auto& i : a) cin >> i; queue<pair<int, int>> q1; queue<e> q2; vector<pair<int, int>> tmp = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; q1.push({x1, y1}); while (q1.size()) { while (q1.size()) { auto [x, y] = q1.front(); q1.pop(); for (auto& [dx, dy] : tmp) { int nx = x + dx, ny = y + dy; if (!(0 <= nx && nx < n && 0 <= ny && ny < m && d[nx][ny] == inf)) continue; if (a[nx][ny] == '.') { d[nx][ny] = d[x][y]; q1.push({nx, ny}); } else { d[nx][ny] = d[x][y] + 1; q2.push({nx, ny, 0, 0}); } } } while (q2.size()) { auto [x, y, p, q] = q2.front(); q2.pop(); if (p == k - 1 || q == k - 1) q1.push({x, y}); for (auto& [dx, dy] : tmp) { int nx = x + dx, ny = y + dy; if (!(0 <= nx && nx < n && 0 <= ny && ny < m && d[nx][ny] == inf)) continue; if (p + abs(dx) < k && q + abs(dy) < k) { d[nx][ny] = d[x][y]; q2.push({nx, ny, p + abs(dx), q + abs(dy)}); } } } } cout << d[x2][y2] << "\n"; } signed main() { // cout.precision(16); ios::sync_with_stdio(false); cin.tie(nullptr); 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...