Submission #928736

#	Time	Username	Problem	Language	Result	Execution time	Memory
928736		GrandTiger1729	Maze (JOI23_ho_t3)	C++17	100 / 100	1168 ms	130400 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>> rgt1(n, vector<int>(m, -1)), rgt2(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++)
        {
            rgt1[i][j] = j + 1;
        }
    }
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < m; j++)
        {
            rgt2[i][j] = i + 1;
        }
    }
    auto able = [&](int i, int j)
    {
        return 0 <= i && i < n && 0 <= j && j < m && !vis[i][j] && g[i][j] == '.';
    };
    auto near = [&](int i, int j)
    {
        return min(abs(i - B.first), abs(j - B.second)) < K && max(abs(i - B.first), abs(j - B.second)) <= K;
    };
    function<int(int, int)> rr1 = [&](int i, int j) -> int
    {
        if (j == -1 || !vis[i][j])
        {
            return j;
        }
        return rgt1[i][j] = rr1(i, rgt1[i][j]);
    };
    function<int(int, int)> rr2 = [&](int i, int j) -> int
    {
        if (i == -1 || !vis[i][j])
        {
            return i;
        }
        return rgt2[i][j] = rr2(rgt2[i][j], 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;
                    if (vis[B.first][B.second])
                    {
                        goto found;
                    }
                }
            }
        }
        while (res2.size())
        {
            auto [i, j] = res2.back();
            res2.pop_back();
            if (near(i, j))
            {
                dis[B.first][B.second] = dis[i][j] + 1;
                goto found;
            }
            for (int ii : {max(0, i - K), min(n - 1, i + K)})
            {
                int jj = rr1(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 = rr1(ii, max(0, j - (K - 1)));
                }
            }
            for (int jj : {max(0, j - K), min(m - 1, j + K)})
            {
                int ii = rr2(max(0, i - (K - 1)), jj);
                while (ii != -1 && ii <= i + (K - 1))
                {
                    res.emplace_back(ii, jj);
                    dis[ii][jj] = dis[i][j] + 1;
                    vis[ii][jj] = 1;
                    ii = rr2(max(0, i - (K - 1)), jj);
                }
            }
        }
    }
    found:
    int ans = dis[B.first][B.second];
    cout << ans << '\n';
    return 0;
}

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