Submission #1253969

#TimeUsernameProblemLanguageResultExecution timeMemory
1253969LucaLucaMMaze (JOI23_ho_t3)C++20
27 / 100
2097 ms265788 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <set> using ll = long long; #define debug(x) #x << " = " << x << '\n' const int INF = 1e9; const int dx[4] = {-1, 0, +1, 0}; const int dy[4] = {0, -1, 0, +1}; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); int n, m, k; std::cin >> n >> m >> k; int x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; x1--, y1--, x2--, y2--; std::vector<std::vector<int>> a(n, std::vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char c; std::cin >> c; if (c == '.') { a[i][j] = 0; } else { a[i][j] = 1; } } } std::vector<std::set<std::pair<int, int>>> thisDistance(n * m + 2); std::vector<std::vector<int>> dist(n, std::vector<int>(m, +INF)); dist[x1][y1] = 0; thisDistance[0].insert({x1, y1}); for (int d = 0; d <= n * m; d++) { std::set<std::pair<int, int>> st; auto dfs = [&](auto &&self, int x, int y) -> void { st.insert({x, y}); for (int dir = 0; dir < 4; dir++) { int xx = x + dx[dir], yy = y + dy[dir]; if (0 <= xx && xx < n && 0 <= yy && yy < m && dist[xx][yy] > d && !a[xx][yy]) { dist[xx][yy] = d; self(self, xx, yy); } } }; for (const auto &[x, y] : thisDistance[d]) { if (dist[x][y] < d) { continue; } dfs(dfs, x, y); st.insert({x, y}); } for (const auto &[x, y] : st) { for (int i = std::max(0, x - k); i <= std::min(n - 1, x + k); i++) { for (int j = std::max(0, y - k); j <= std::min(m - 1, y + k); j++) { if (dist[i][j] == +INF && std::abs(i - x) + std::abs(j - y) < 2 * k) { dist[i][j] = d + 1; thisDistance[d + 1].insert({i, j}); } } } } } std::cout << dist[x2][y2]; 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...