Submission #1123963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123963		LucaIlie	Maze (JOI23_ho_t3)	C++20	8 / 100	644 ms	353688 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

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 = 2451;
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];
priority_queue<elempq> pq;

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

    scanf( "%d%d%d", &n, &m, &k );
    scanf( "%d%d", &sl, &sc );
    scanf( "%d%d", &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 };
        }
    }
    for ( int l = 1; l <= n; l++ ) {
        char ch;
        scanf( "%c", &ch );
        for ( int c = 1; c <= m; c++ ) {
            scanf( "%c", &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() && minDist[4][gl][gc].dist == INF ) {
        cell a = pq.top().c;
        distancee dd = pq.top().d;
        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 ( minDist[dir][l][c] < dd )
            continue;

        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 {
            int parit = 3;
            distancee newDist = minDist[dir][l][c];
            if ( newDist.distL == k ) {
                if ( newDist.distC == k ) {
                    newDist.dist++;
                    newDist.dir = 0;
                    newDist.distL = newDist.distC = 1;
                } else {
                    parit -= 1;
                    if ( newDist.distC == 1 )
                        newDist.dir += 2;
                    newDist.distC++;
                }
            } else if ( newDist.distC == k ) {
                parit -= 2;
                if ( newDist.distL == 1 )
                    newDist.dir += 2;
                newDist.distL++;
            } else if ( newDist.distL == 1 ) {
                if ( newDist.distC != 1 ) {
                    parit -= 1;
                    newDist.distC++;
                }
            } else if ( newDist.distC == 1 ) {
                parit -= 2;
                newDist.distL++;
            }
            for ( int d = 0; d < 4; d++ ) {
                int newL = l + dl[d], newC = c + dc[d];
                if ( !isBlocked[newL][newC] ) {
                    distancee nn = minDist[dir][l][c];
                    nn.dir = 4;
                    nn.dist++;
                    nn.distL = nn.distC = 0;
                    if ( nn < minDist[nn.dir][newL][newC] ) {
                        minDist[nn.dir][newL][newC] = nn;
                        pq.push( { nn.dir, newL, newC, minDist[nn.dir][newL][newC] } );
                    }
                }
                if ( d % 2 == 0 && !(parit & 1) )
                    continue;
                if ( d % 2 == 1 && !(parit & 2) )
                    continue;
                if ( k != 1 && minDist[dir][l][c].distL == 1 && minDist[dir][l][c].distC == 1 ) {
                    distancee nn = newDist;
                    if ( d % 2 == 0 ) {
                        newDist.distL++;
                        newDist.dir = 0;
                    } else {
                        newDist.distC++;
                        newDist.dir = 1;
                    }
                    newDist = nn;
                }
                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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf( "%d%d%d", &n, &m, &k );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf( "%d%d", &sl, &sc );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf( "%d%d", &gl, &gc );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf( "%c", &ch );
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |             scanf( "%c", &ch );
      |             ~~~~~^~~~~~~~~~~~~

• 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