Submission #1123840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123840		LucaIlie	Maze (JOI23_ho_t3)	C++20	8 / 100	702 ms	285760 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct cell {
    int dir, l, c;
};

struct distancee {
    int dist, dir, distL, distC;
};

bool operator < ( distancee a, distancee b ) {
    if ( a.dist == b.dist ) {
        return max( a.distL, a.distC ) < max( b.distL, b.distC );
    }
    return a.dist < b.dist;
}

struct elempq {
    cell c;
    distancee d;

    bool operator < ( const elempq &x ) const {
        return x.d < d;
    }
};

const int MAX_N = 2500;
const int INF = 1e7;
int dl[4] = { 1, 0, -1, 0 }, dc[4] = { 0, 1, 0, -1 };
vector<distancee> minDist[4][MAX_N];
vector<bool> isBlocked[MAX_N], vis[4][MAX_N];
priority_queue<elempq> pq;

int main() {
    int n, m, k, sl, sc, gl, gc;

    cin >> n >> m >> k;
    cin >> sl >> sc;
    cin >> gl >> gc;
    for ( int l = 0; l <= n + 1; l++ ) {
        isBlocked[l].resize( m + 2 );
        for ( int d = 0; d < 4; d++ ) {
            minDist[d][l].resize( m + 2 );
            for ( int c = 0; c <= m + 1; c++ )
                minDist[d][l][c] = { INF, d, 0, 0 };
            vis[d][l].resize( m + 2 );
        }
    }
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            char ch;
            cin >> ch;
            isBlocked[l][c] = (ch == '#');
        }
    }
    for ( int l = 0; l <= n + 1; l++ ) {
        isBlocked[l][0] = isBlocked[l][m + 1] = true;
        for ( int d = 0; d < 4; d++ )
            minDist[d][l][0] = minDist[d][l][m + 1] = { -INF, d, 0, 0 };
    }
    for ( int c = 0; c <= m + 1; c++ ) {
        isBlocked[0][c] = isBlocked[n + 1][c] = true;
        for ( int d = 0; d < 4; d++ )
            minDist[d][0][c] = minDist[d][n + 1][c] = { -INF, d, 0, 0 };
    }

    minDist[0][sl][sc] = { 0, 0, 0, 0 };
    pq.push( { 0, sl, sc, minDist[0][sl][sc] } );
    while ( !pq.empty() ) {
        cell a = pq.top().c;
        pq.pop();

        int dir = a.dir, l = a.l, c = a.c;
        if ( vis[dir][l][c] )
            continue;
        vis[dir][l][c] = true;

        //printf( "celula %d %d %d cu distanta %d %d %d %d\n", dir, l, c, minDist[dir][l][c].dir, minDist[dir][l][c].dist, minDist[dir][l][c].distL, minDist[dir][l][c].distC );

        if ( !isBlocked[l][c] ) {
            for ( int d = 0; d < 4; d++ ) {
                int newL = l + dl[d], newC = c + dc[d];
                distancee newDist = minDist[dir][l][c];
                if ( isBlocked[newL][newC] ) {
                    newDist.dist = minDist[dir][l][c].dist + 1;
                    newDist.dir = d % 2;
                    newDist.distL = newDist.distC = 1;
                }
                if ( newDist < minDist[newDist.dir][newL][newC] ) {
                    minDist[newDist.dir][newL][newC] = newDist;
                    pq.push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
                }
            }
        } else {
            for ( int d = 0; d < 4; d++ ) {
                int newL = l + dl[d], newC = c + dc[d];
                distancee newDist = minDist[dir][l][c];
                if ( !isBlocked[newL][newC] ) {
                    newDist.dir = 0;
                    newDist.distL = newDist.distC = 0;
                } else {
                    if ( newDist.distL == k && newDist.distC == k ) {
                        newDist.dist++;
                        newDist.dir = 0;
                        newDist.distL = newDist.distC = 1;
                    } else if ( newDist.distL == k ) {
                        if ( d % 2 == 1 )
                            continue;
                        newDist.distC++;
                    } else if ( newDist.distC == k ) {
                        if ( d % 2 == 0 )
                            continue;
                        newDist.distL++;
                    } else if ( newDist.distL == 1 && newDist.distC == 1 ) {
                        if ( d % 2 == 0 )
                            newDist.distL++;
                        else
                            newDist.distC++;
                    } else if ( newDist.distL == 1 ) {
                        if ( d % 2 == 0 )
                            continue;
                        newDist.distC++;
                    } else if ( newDist.distC == 1 ) {
                        if ( d % 2 == 1 )
                            continue;
                        newDist.distL++;
                    } else {
                        cout << "CUM\n";
                        exit( 1 );
                    }
                }
                if ( newDist < minDist[newDist.dir][newL][newC] ) {
                    minDist[newDist.dir][newL][newC] = newDist;
                    pq.push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
                }
            }
        }
    }

    int ans = minDist[0][gl][gc].dist;
    for ( int l = 1; l <= n; l++ ) {
        for ( int c = 1; c <= m; c++ ) {
            if ( !isBlocked[l][c] && abs( l - gl ) <= k - 1 && abs( c - gc ) <= k - 1 )
                ans = min( ans, minDist[0][l][c].dist + 1 );
        }
    }

    cout << ans << "\n";

    return 0;
}

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