제출 #884780

#제출 시각아이디문제언어결과실행 시간메모리
884780AlcabelMaze (JOI23_ho_t3)C++17
27 / 100
513 ms40868 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 1e7; const pair<int, int> deltas[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; vector<string> a; vector<vector<int>> vis, dist; int r, c, mini, minj, maxi, maxj, tt; vector<pair<int, int>> listVis; void dfs(int i, int j) { listVis.emplace_back(i, j); vis[i][j] = tt; for (const auto& [di, dj] : deltas) { if (i + di >= mini && i + di <= maxi && j + dj >= minj && j + dj <= maxj && vis[i + di][j + dj] < tt && dist[i + di][j + dj] >= dist[i][j]) { dist[i + di][j + dj] = dist[i][j]; dfs(i + di, j + dj); } } } void solve() { int n; cin >> r >> c >> n; int sr, sc, gr, gc; cin >> sr >> sc >> gr >> gc; --sr, --sc, --gr, --gc; a.resize(r); for (int i = 0; i < r; ++i) { cin >> a[i]; } vis.resize(r, vector<int>(c, -1)); dist.resize(r, vector<int>(c, inf)); vector<pair<int, int>> q[2], ext; dist[sr][sc] = 0; q[0].emplace_back(sr, sc); int layer = 0; tt = -1; while (dist[gr][gc] == inf) { while (!q[layer].empty()) { auto [i, j] = q[layer].back(); q[layer].pop_back(); ext.emplace_back(i, j); for (const auto& [di, dj] : deltas) { int newi = i + di, newj = j + dj; if (newi >= 0 && newi < r && newj >= 0 && newj < c && a[newi][newj] == '.' && dist[newi][newj] == inf) { dist[newi][newj] = dist[i][j]; q[layer].emplace_back(newi, newj); } } } for (int iter = 0; iter < 4; ++iter) { ++tt; sort(ext.begin(), ext.end()); if (iter == 0) { // up for (auto [i, j] : ext) { mini = max(0, i - n), minj = max(0, j - n + 1); maxi = min(r - 1, i - 1), maxj = min(c - 1, j + n - 1); if (i - 1 >= 0 && vis[i - 1][j] < tt && dist[i - 1][j] > dist[i][j]) { dist[i - 1][j] = dist[i][j] + 1; dfs(i - 1, j); } } } else if (iter == 1) { // left for (auto [j, i] : ext) { i = -i; mini = max(0, i - n + 1), minj = max(0, j - n); maxi = min(r - 1, i + n - 1), maxj = min(c - 1, j - 1); if (j - 1 >= 0 && vis[i][j - 1] < tt && dist[i][j - 1] > dist[i][j]) { dist[i][j - 1] = dist[i][j] + 1; dfs(i, j - 1); } } } else if (iter == 2) { // down for (auto [i, j] : ext) { i = -i, j = -j; mini = max(0, i + 1), minj = max(0, j - n + 1); maxi = min(r - 1, i + n), maxj = min(c - 1, j + n - 1); if (i + 1 < r && vis[i + 1][j] < tt && dist[i + 1][j] > dist[i][j]) { dist[i + 1][j] = dist[i][j] + 1; dfs(i + 1, j); } } } else { // right for (auto [j, i] : ext) { j = -j; mini = max(0, i - n + 1), minj = max(0, j + 1); maxi = min(r - 1, i + n - 1), maxj = min(c - 1, j + n); if (j + 1 < c && vis[i][j + 1] < tt && dist[i][j + 1] > dist[i][j]) { dist[i][j + 1] = dist[i][j] + 1; dfs(i, j + 1); } } } for (int i = 0; i < (int)ext.size(); ++i) { ext[i].first = -ext[i].first; swap(ext[i].first, ext[i].second); } } ext.clear(); sort(listVis.begin(), listVis.end()); listVis.resize(unique(listVis.begin(), listVis.end()) - listVis.begin()); layer ^= 1; swap(q[layer], listVis); listVis.clear(); } cout << dist[gr][gc] << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T = 1; cin >> T; while (T--) { solve(); cerr << "-----------\n"; cout << "-----------\n"; } #else int T = 1; // cin >> T; while (T--) { solve(); } #endif 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...