Submission #1123933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123933		LucaIlie	Maze (JOI23_ho_t3)	C++20	86 / 100	2001 ms	356972 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 ) {
        int valA = (a.dir < 2 ? max( a.distL, a.distC ) : min( a.distL, a.distC ));
        int valB = (b.dir < 2 ? max( b.distL, b.distC ) : min( b.distL, b.distC ));
        return valA < valB;
    }
    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[5][MAX_N];
vector<bool> isBlocked[MAX_N], vis[5][MAX_N];
priority_queue<elempq> pq;

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    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 < 5; 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 < 5; 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 < 5; d++ )
            minDist[d][0][c] = minDist[d][n + 1][c] = { -INF, d, 0, 0 };
    }

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

        int dir = a.dir, l = a.l, c = a.c;
        //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 ( dir == 4 ) {
            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 = 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 = 4;
                    newDist.dist++;
                    newDist.distL = newDist.distC = 0;
                    if ( newDist < minDist[newDist.dir][newL][newC] ) {
                        minDist[newDist.dir][newL][newC] = newDist;
                        pq.push( { newDist.dir, newL, newC, minDist[newDist.dir][newL][newC] } );
                    }
                }
                newDist = minDist[dir][l][c];
                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 == 0 )
                        continue;
                    if ( newDist.distC == 1 )
                        newDist.dir += 2;
                    newDist.distC++;
                } else if ( newDist.distC == k ) {
                    if ( d % 2 == 1 )
                        continue;
                    if ( newDist.distL == 1 )
                        newDist.dir += 2;
                    newDist.distL++;
                } else if ( newDist.distL == 1 && newDist.distC == 1 ) {
                    if ( d % 2 == 0 ) {
                        newDist.distL++;
                        newDist.dir = 0;
                    } else {
                        newDist.distC++;
                        newDist.dir = 1;
                    }
                } 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[4][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[4][l][c].dist + 1 );
        }
    }

    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: 0 / 8
• Subtask 8: 0 / 6