Cod sursa(job #1703418)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 16 mai 2016 21:33:41
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <bits/stdc++.h>

const int DIM = 1 << 9;
const int EXP = 1 << 3;
const int INF = 0x3f3f3f3f;
using namespace std;

int Dp[DIM * DIM * EXP], A[DIM * DIM], N, M, xst, yst, xfn, yfn, minim;
vector <int> my_list[EXP >> 1]; int node, xx, yy, dd;

int Dx[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int Dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };

class input_reader {
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        char buffer[SIZE]; int cursor;

        inline void advance() {
            if( ++cursor == SIZE ) {
                cursor = 0;
                fread( buffer, SIZE, 1, input_file );
            }

            return;
        }

        inline char current() {
            return buffer[cursor];
        }
    public:
        input_reader( const char *file_name, const char *file_type ) {
            input_file = fopen( file_name, file_type ); cursor = 0;
            fread( buffer, SIZE, 1, input_file );
        }

        input_reader &operator >>( int &value ) {
            value = 0;

            while( current() < '0' || current() > '9' )
                advance();

            while( current() >= '0' && current() <= '9' ) {
                value = value * 10 + ( current() - '0' );
                advance();
            }

            return *this;
        }
} input_file( "car.in", "r" );
FILE *output_file = fopen( "car.out", "w" );

int main() {

    input_file >> N >> M >> xst >> yst >> xfn >> yfn;
    memset( Dp, INF, sizeof(Dp) );

    for( int i = 1; i <= N; i ++ )
    for( int j = 1; j <= M; j ++ )
        input_file >> A[ (i << 9) + j];

    for( int d = 0; d < 8; d ++ ) {
        Dp[(xst << 12) + (yst << 3) + d] = 0;
        my_list[0].push_back( (xst << 12) + (yst << 3) + d );
    }

    for( int c = 0; my_list[0].size() + my_list[1].size() + my_list[2].size() + my_list[3].size() != 0; c ++ ) {
        while( my_list[c & 3].size() != 0 ) {
            node = my_list[c & 3][ my_list[c & 3].size() - 1 ];
            xx = (node >> 12) & (DIM - 1);
            yy = (node >> 3 ) & (DIM - 1);
            dd = node & (EXP - 1);
            my_list[c & 3].pop_back();

            if( Dp[ (xx << 12) + (yy << 3) + dd ] < c )
                continue;

            if( xx + Dx[ dd ] >= 1 && xx + Dx[ dd ] <= N ) {
            if( yy + Dy[ dd ] >= 1 && yy + Dy[ dd ] <= M ) {
            if( A[ ((xx + Dx[ dd ]) << 9) + yy + Dy[ dd ] ] == 0 ) {
            if( Dp[ ((xx + Dx[ dd ]) << 12) + ((yy + Dy[ dd ]) << 3) + dd ] > c ) {
                Dp[ ((xx + Dx[ dd ]) << 12) + ((yy + Dy[ dd ]) << 3) + dd ] = c;
                my_list[c & 3].push_back( ((xx + Dx[ dd ]) << 12) + ((yy + Dy[ dd ]) << 3) + dd );
            }}}}

            for( int p = -2, dir = ( dd + 8 + p ) & 7; p <= 2; p ++, dir = ( dir + 1 ) & 7 ) {
                if( Dp[ (xx << 12) + (yy << 3) + dir ] > Dp[ (xx << 12) + (yy << 3) + dd ] + abs(p) ) {
                    Dp[ (xx << 12) + (yy << 3) + dir ] > Dp[ (xx << 12) + (yy << 3) + dd ] + abs(p);
                    my_list[ (c + abs(p)) & 3 ].push_back( (xx << 12) + (yy << 3) + dir );
                }
            }
        }
    }

    minim = INF;
    for( int d = 0; d < 8; d ++ )
        minim = min( minim, Dp[ (xfn << 12) + (yfn << 3) + d ] );

    if( minim == INF )
        fprintf( output_file, "%d\n", -1 );
    else
        fprintf( output_file, "%d\n", minim );

    return 0;
}