Submission #928462

#	Time	Username	Problem	Language	Result	Execution time	Memory
928462		GrandTiger1729	Maze (JOI23_ho_t3)	C++17	51 / 100	2049 ms	39064 KiB

Main

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

const int B = 30, 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>> rgt(n, vector<int>(m, -1));
    vector<vector<bool>> vis(n, vector<bool>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m - 1; j++)
        {
            rgt[i][j] = j + 1;
        }
    }
    auto able = [&](int i, int j)
    {
        return 0 <= i && i < n && 0 <= j && j < m && !vis[i][j] && g[i][j] == '.';
    };
    function<int(int, int)> rr = [&](int i, int j) -> int
    {
        if (j == -1 || !vis[i][j])
        {
            return j;
        }
        return rgt[i][j] = rr(i, rgt[i][j]);
    };
    vector<vector<int>> dis(n, vector<int>(m, INF));
    vector<pair<int, int>> res;
    res.push_back(A);
    vis[A.first][A.second] = 1;
    dis[A.first][A.second] = 0;
    while (res.size())
    {
        vector<pair<int, int>> res2;
        while (res.size())
        {
            auto [i, j] = res.back();
            res2.emplace_back(i, j);
            res.pop_back();
            for (auto &[dx, dy] : vector<pair<int, int>>{{1, 0}, {0, 1}, {-1, 0}, {0, -1}})
            {
                if (able(i + dx, j + dy))
                {
                    res.emplace_back(i + dx, j + dy);
                    dis[i + dx][j + dy] = dis[i][j];
                    vis[i + dx][j + dy] = 1;
                }
            }
        }
        while (res2.size())
        {
            auto [i, j] = res2.back();
            res2.pop_back();
            for (int ii = max(0, i - K); ii <= min(n - 1, i + K); ii++)
            {
                int jj = rr(ii, max(0, j - (K - 1)));
                while (jj != -1 && jj <= j + (K - 1))
                {
                    res.emplace_back(ii, jj);
                    dis[ii][jj] = dis[i][j] + 1;
                    vis[ii][jj] = 1;
                    jj = rr(ii, max(0, j - (K - 1)));
                }
            }
            for (int ii = max(0, i - (K - 1)); ii <= min(n - 1, i + (K - 1)); ii++)
            {
                int jj = rr(ii, max(0, j - K));
                while (jj != -1 && jj <= j + K)
                {
                    res.emplace_back(ii, jj);
                    dis[ii][jj] = dis[i][j] + 1;
                    vis[ii][jj] = 1;
                    jj = rr(ii, max(0, j - K));
                }
            }
        }
    }
    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