Submission #1215495

#TimeUsernameProblemLanguageResultExecution timeMemory
1215495stefanneaguMaze (JOI23_ho_t3)C++17
51 / 100
2096 ms30276 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 1e9; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, 1, -1}; struct str { int a, b, c; const bool operator < (str ult) const { return a > ult.a; } }; priority_queue<str> dq; vector<vector<int>> rasp; vector<vector<bool>> mat; int n, m, k; int si, ei, sj, ej; bool in(int a, int b) { return (min({a, b, n - a + 1, m - b + 1}) > 0); } bool in_timbra(int i, int j) { if ((ei == i - k && ej == j - k) || (ei == i + k && ej == j - k) || (ei == i - k && ej == j + k) || (ei == i + k && ej == j + k)) { return 0; } if (i - k <= ei && ei <= i + k && j - k <= ej && ej <= j + k) { return 1; } return 0; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m >> k >> si >> sj >> ei >> ej; rasp.resize(n + 1, vector<int>(m + 1, inf)); mat.resize(n + 1, vector<bool>(m + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char ch; cin >> ch; mat[i][j] = (ch == '.' ? 0 : 1); } } dq.push({0, si, sj}); rasp[si][sj] = 0; int ans = inf; while (!dq.empty()) { auto [val, i, j] = dq.top(); dq.pop(); for (int D = 0; D < 4; D++) { if (in(i + dx[D], j + dy[D]) && !mat[i + dx[D]][j + dy[D]] && rasp[i + dx[D]][j + dy[D]] > rasp[i][j]) { rasp[i + dx[D]][j + dy[D]] = rasp[i][j]; dq.push({val, i + dx[D], j + dy[D]}); } } if (in_timbra(i, j)) { ans = min(ans, rasp[i][j] + 1); } // lat sus for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) { if (rasp[max(1, i - k)][j2] > rasp[i][j] + 1) { rasp[max(1, i - k)][j2] = rasp[i][j] + 1; dq.push({val + 1, max(1, i - k), j2}); } } // lat dreapta for (int i2 = max(1, i - k + 1); i2 <= min(n, i + k - 1); i2++) { if (rasp[i2][min(m, j + k)] > rasp[i][j] + 1) { rasp[i2][min(m, j + k)] = rasp[i][j] + 1; dq.push({val + 1, i2, min(m, j + k)}); } } // lat jos for (int j2 = max(1, j - k + 1); j2 <= min(m, j + k - 1); j2++) { if (rasp[min(n, i + k)][j2] > rasp[i][j] + 1) { rasp[min(n, i + k)][j2] = rasp[i][j] + 1; dq.push({val + 1, min(n, i + k), j2}); } } // lat stanga for (int i2 = max(1, i - k + 1); i2 <= min(n, i + k - 1); i2++) { if (rasp[i2][max(1, j - k)] > rasp[i][j] + 1) { rasp[i2][max(1, j - k)] = rasp[i][j] + 1; dq.push({val + 1, i2, max(1, j - k)}); } } } cout << min(ans, rasp[ei][ej]); return 0; }
#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...