Submission #1291161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291161		chikien2009	Maze (JOI23_ho_t3)	C++20	100 / 100	702 ms	152676 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};

int r, c, k, x, y, a, b;
vector<vector<int>> dist;
vector<string> s;
array<int, 5> nxt, cur;
deque<array<int, 5>> dq;

inline bool Valid(array<int, 5> inp)
{
    return (0 <= inp[0] && inp[0] < r &&
            0 <= inp[1] && inp[1] < c &&
            (inp[2] < 4 || inp[3] < k) &&
            inp[4] <= k &&
            dist[nxt[0]][nxt[1]] == 1e9);
}

inline void Expand()
{
    for (int i = 0; i < dq.size(); ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            nxt[0] = dq[i][0] + dx[j];
            nxt[1] = dq[i][1] + dy[j];
            nxt[2] = -1;
            nxt[3] = 0;
            nxt[4] = 0;
            if (Valid(nxt) && s[nxt[0]][nxt[1]] == '.')
            {
                dist[nxt[0]][nxt[1]] = dist[dq[i][0]][dq[i][1]];
                dq.push_back(nxt);
            }
        }
    }
}

inline void Explode(int val)
{
    deque<array<int, 5>> temp;
    while (!dq.empty())
    {
        cur = dq.front();
        dq.pop_front();
        for (int i = 0; i < 8; ++i)
        {
            nxt[0] = cur[0] + dx[i];
            nxt[1] = cur[1] + dy[i];
            nxt[2] = i;
            nxt[3] = 1 + cur[3] * (cur[2] == nxt[2]);
            nxt[4] = cur[4] + 1;
            if (Valid(nxt))
            {
                dist[nxt[0]][nxt[1]] = val;
                dq.push_back(nxt);
                temp.push_back({nxt[0], nxt[1], -1, 0, 0});
            }
        }
    }
    swap(dq, temp);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c >> k >> x >> y >> a >> b;
    x--;
    y--;
    a--;
    b--;
    dist.resize(r, vector<int>(c, 1e9));
    s.resize(r);
    for (int i = 0; i < r; ++i)
    {
        cin >> s[i];
    }
    if (s[x][y] == '#')
    {
        for (int i = x - k + 1; i <= x + k - 1; ++i)
        {
            for (int j = y - k + 1; j < y + k - 1; ++j)
            {
                if (0 <= i && i < r && 0 <= j && j < c)
                {
                    dist[i][j] = 1;
                    dq.push_back({i, j, -1, 0, 0});
                }
            }
        }
    }
    else
    {
        dist[x][y] = 0;
        dq.push_back({x, y, -1, 0, 0});
    }
    for (int i = 1; !dq.empty(); ++i)
    {
        Expand();
        Explode(i);
    }   
    cout << dist[a][b];
    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