Submission #928313

#	Time	Username	Problem	Language	Result	Execution time	Memory
928313		GrandTiger1729	Maze (JOI23_ho_t3)	C++17	51 / 100	2043 ms	109564 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 10;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, K;
    cin >> n >> m >> K;
    pair<int, int> A, B;
    cin >> A.first >> A.second >> B.first >> B.second;
    A.first--, A.second--, B.first--, B.second--;
    vector<string> g(n);
    for (int i = 0; i < n; i++)
    {
        cin >> g[i];
    }
    vector<vector<int>> lft(n, vector<int>(m, -1)), rgt(n, vector<int>(m, -1));
    vector<set<int>> vis(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            vis[i].insert(j);
        }
    }
    auto able = [&](int i, int j)
    {
        return 0 <= i && i < n && 0 <= j && j < m && vis[i].find(j) != vis[i].end() && g[i][j] == '.';
    };
    vector<vector<int>> dis(n, vector<int>(m, INF));
    deque<pair<int, int>> dq;
    dq.push_back(A);
    vis[A.first].erase(A.second);
    dis[A.first][A.second] = 0;
    while (dq.size())
    {
        vector<pair<int, int>> res;
        while (dq.size())
        {
            auto [i, j] = dq.front();
            res.emplace_back(i, j);
            dq.pop_front();
            for (auto &[dx, dy] : vector<pair<int, int>>{{1, 0}, {0, 1}, {-1, 0}, {0, -1}})
            {
                if (able(i + dx, j + dy))
                {
                    dq.emplace_front(i + dx, j + dy);
                    dis[i + dx][j + dy] = dis[i][j];
                    vis[i + dx].erase(j + dy);
                }
            }
        }
        while (res.size())
        {
            auto [i, j] = res.back();
            res.pop_back();
            for (int ii = max(0, i - K); ii <= min(n - 1, i + K); ii++)
            {
                auto it = vis[ii].lower_bound(j - (K - 1));
                while (it != vis[ii].end() && *it <= j + (K - 1))
                {
                    dq.emplace_back(ii, *it);
                    dis[ii][*it] = dis[i][j] + 1;
                    it = vis[ii].erase(it);
                }
            }
            for (int ii = max(0, i - (K - 1)); ii <= min(n - 1, i + (K - 1)); ii++)
            {
                auto it = vis[ii].lower_bound(j - K);
                while (it != vis[ii].end() && *it <= j + K)
                {
                    dq.emplace_back(ii, *it);
                    dis[ii][*it] = dis[i][j] + 1;
                    it = vis[ii].erase(it);
                }
            }
        }
    }
    int ans = dis[B.first][B.second];
    cout << ans << '\n';
    return 0;
}

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