Submission #884780

#	Time	Username	Problem	Language	Result	Execution time	Memory
884780		Alcabel	Maze (JOI23_ho_t3)	C++17	27 / 100	513 ms	40868 KiB

Main

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6