Cod sursa(job #2414486)

Utilizator robx12lnLinca Robert robx12ln Data 24 aprilie 2019 16:51:00
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<bits/stdc++.h>
using namespace std;

FILE * fin = fopen("car.in", "r");
FILE * fout = fopen("car.out", "w");

const int Sz = 1e6;

int N, M, is, js, ifin, jfin, a[505][505];
int dp[505][505][8];
int di[] = { -1, -1, +0, +1, +1, +1, +0, -1 };
int dj[] = { +0, +1, +1, +1, +0, -1, -1, -1 };
bool f[505][505][8];
queue< pair< pair<int,int>, int > > dq;

inline bool inmat( int i, int j ){
    if( 1 <= i && i <= N && 1 <= j && j <= M )
        return true;
    return false;
}

char buffer[Sz];
int pos = 0;

inline void Read( int &numar ){
    numar = 0;
    while( buffer[pos] < '0' || buffer[pos] > '9' ){
        pos++;
        if( pos == Sz )
            pos = 0, fread( buffer, Sz, 1, fin );
    }
    while( buffer[pos] >= '0' && buffer[pos] <= '9' ){
        numar = numar * 10 + ( buffer[pos] - '0' );
        pos++;
        if( pos == Sz )
            pos = 0, fread( buffer, Sz, 1, fin );
    }
}

int main(){
    fread( buffer, Sz, 1, fin );

    Read( N ); Read( M );
    Read( is ); Read( js ); Read( ifin ); Read( jfin );
    for( int i = 1; i <= N; i++ )
        for( int j = 1; j <= M; j++ )
            Read( a[i][j] );

    memset( dp, 0x3f3f3f3f, sizeof(dp) );

    for( int d = 0; d <= 7; d++ ){
        dp[is][js][d] = 0;
        f[is][js][d] = true;
        dq.push( { {is, js}, d } );
    }

    while( !dq.empty() ){

        int ic = dq.front().first.first;
        int jc = dq.front().first.second;
        int dir = dq.front().second;
        dq.pop();

        int iv, jv, new_dir;

        ///mentin directia
        iv = ic + di[dir];
        jv = jc + dj[dir];
        if( inmat( iv, jv ) == true && a[iv][jv] == 0 && dp[iv][jv][dir] > dp[ic][jc][dir] ){
            dp[iv][jv][dir] = dp[ic][jc][dir];
            if( f[iv][jv][dir] == false )
                f[iv][jv][dir] = true, dq.push( { {iv, jv}, dir } );
        }

        ///mutare la stanga cu 45 grade
        new_dir = ( ( dir == 0 ) ? 7 : (dir - 1) );
        if( dp[ic][jc][new_dir] > dp[ic][jc][dir] + 1 ){
            dp[ic][jc][new_dir] = dp[ic][jc][dir] + 1;
            if( f[ic][jc][new_dir] == false )
                f[ic][jc][new_dir] = true, dq.push( { {ic, jc}, new_dir } );
        }

        ///mutare la dreapta cu 45 grade
        new_dir = ( ( dir == 7 ) ? 0 : (dir + 1) );
        if( dp[ic][jc][new_dir] > dp[ic][jc][dir] + 1 ){
            dp[ic][jc][new_dir] = dp[ic][jc][dir] + 1;
            if( f[ic][jc][new_dir] == false )
                f[ic][jc][new_dir] = true, dq.push( { {ic, jc}, new_dir } );
        }

        f[ic][jc][dir] = false;
    }

    int ans = 0x3f3f3f3f;
    for( int d = 0; d <= 7; d++ )
        ans = min( ans, dp[ifin][jfin][d] );
    ans = ( ans == 0x3f3f3f3f ) ? -1 : ans;
    fprintf( fout, "%d\n", ans );
    return 0;
}