Cod sursa(job #1703378)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 16 mai 2016 21:01:28
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 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;
struct q_node{ int x, y, d; }; vector <q_node> my_list[EXP >> 1];

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][j];

    for( int d = 0; d < 8; d ++ ) {
        Dp[xst][yst][d] = 0;
        my_list[0].push_back( {xst, yst, 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 ) {
            q_node node = my_list[c & 3][ my_list[c & 3].size() - 1 ];
            my_list[c & 3].pop_back();

            if( Dp[ node.x ][ node.y ][ node.d ] < c )
                continue;

            if( node.x + Dx[ node.d ] >= 1 && node.x + Dx[ node.d ] <= N ) {
            if( node.y + Dy[ node.d ] >= 1 && node.y + Dy[ node.d ] <= M ) {
            if( A[ node.x + Dx[ node.d ] ][ node.y + Dy[ node.d ] ] == 0 ) {
            if( Dp[ node.x + Dx[ node.d ] ][ node.y + Dy[ node.d ] ][ node.d ] > c ) {
                Dp[ node.x + Dx[ node.d ] ][ node.y + Dy[ node.d ] ][ node.d ] = c;
                my_list[c & 3].push_back( {node.x + Dx[ node.d ], node.y + Dy[ node.d ], node.d } );
            }}}}

            for( int p = -2, dir = ( node.d + 8 + p ) & 7; p <= 2; p ++, dir = ( dir + 1 ) & 7 ) {
                if( Dp[ node.x ][ node.y ][ dir ] > Dp[ node.x ][ node.y ][ node.d ] + abs(p) ) {
                    Dp[ node.x ][ node.y ][ dir ] = Dp[ node.x ][ node.y ][ node.d ] + abs(p);
                    my_list[ (c + abs(p)) & 3 ].push_back( {node.x, node.y, dir} );
                }
            }
        }
    }

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

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

    return 0;
}