Submission #1182664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182664		jerzyk	Maze (JOI23_ho_t3)	C++20	100 / 100	534 ms	55640 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 6'000'007;
int tab[N];
vector<pair<int, int>> roza;
int n, m;
int dis[N];

void DoRoza()
{
    for(int i = -1; i <= 1; ++i)
        for(int j = -1; j <= 1; ++j)
            if(i != 0 || j != 0)
                roza.pb(make_pair(i, j));
}

void BFS(int s1, int s2, int k)
{
    queue<int> q0, q1;
    for(int i = 1; i <= n * m; ++i) dis[i] = II;
    int v, i, j;
    v = (s1 - 1) * m + s2;
    dis[v] = tab[v];
    q0.push(v);
    while((int)q0.size() + (int)q1.size() > 0)
    {
        if((int)q0.size() == 0 || ((int)q1.size() > 0 && dis[q1.front()] <= dis[q0.front()]))
        {v = q1.front(); q1.pop();}
        else
        {v = q0.front(); q0.pop();}
        i = (v + m - 1) / m; j = v - (i - 1) * m;
        //if(dis[v] == 0)
            //cout << "D: " << "{ " << i << " " << j << " }: " << dis[v] << "\n";
        for(int l = 0; l < (int)roza.size(); ++l)
        {
            int ni = i + roza[l].st, nj = j + roza[l].nd;
            int ne = (ni - 1) * m + nj;
            if(ni < 1 || ni > n || nj < 1 || nj > m) continue;
            if((ni == i || nj == j) && dis[v] % k == 0 && !tab[ne] && dis[v] < dis[ne])
            {
                //cout << "E0: " << "{ " << i << " " << j << " } -> { " << ni << " " << nj << " }\n";
                dis[ne] = dis[v];
                q0.push(ne);
            }else if(dis[v] + 1 < dis[ne] && (dis[v] % k != 0 || (ni == i || nj == j)))
            {
                dis[ne] = dis[v] + 1;
                q1.push(ne);
            }
        }
    }
}

void Solve()
{
    int k, s1, s2, e1, e2;
    string s;
    cin >> n >> m >> k;
    cin >> s1 >> s2;
    cin >> e1 >> e2;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s;
        for(int j = 1; j <= m; ++j)
            if(s[j - 1] == '#') tab[(i - 1) * m + j] = 1;
    }
    BFS(s1, s2, k);
    int ans = dis[(e1 - 1) * m + e2];
    ans = (ans + k - 1) / k;
    cout << ans << "\n";
}

int main()
{
    DoRoza();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    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