Cod sursa(job #1232266)

Utilizator xtreme77Patrick Sava xtreme77 Data 22 septembrie 2014 16:58:22
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <algorithm>

#define mp make_pair

const char IN [ ] = "car.in" ;
const char OUT [ ] = "car.out" ;
const int MAX = 514 ;
const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair < int , int > P ;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

int mat [ MAX ] [ MAX ] , d [ 8 ] [ MAX ] [ MAX ] ;

int dx [ ] = { 1 , 1 , 0 , -1 , -1 , -1 , 0 , 1 } ;
int dy [ ] = { 0 , 1 , 1 , 1 , 0 , -1 , -1 , -1 } ;

queue < pair < P , int > > Q [ 2 ] ;

void soll ( int &x , int y )
{
    if ( x > y )
        x = y ;
}
int main(              )
{
    int n , m ;
    fin >> n >> m ;
    int startx , starty , finx , finy ;
    fin >> startx >> starty >> finx >> finy ;
    for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= m ; ++ j )
        {
            fin >> mat [ i ] [ j ] ;
            mat [ i ] [ j ] = 1 - mat [ i ] [ j ] ;
        }
    memset ( d , INF , sizeof ( d ) ) ;
    for ( int i = 0 ; i < 8 ; ++ i )
    {
        Q [ 0 ].push ( mp ( mp ( startx , starty ) , i ) ) ;
        d [ i ] [ startx ] [ starty ] = 0 ;
    }
    int prim = 0 ;
    int secund = 1 ;

    while ( !Q [ prim ].empty ( ) or !Q [ secund ].empty ( ) )
    {
        if ( Q [ prim ].empty ( ) )
            swap ( prim , secund ) ;
        int i = Q [ prim ].front ().first.first ;
        int j = Q [ prim ].front ().first.second ;
        int dir = Q [ prim ].front ().second ;

        Q [ prim ].pop ( ) ;

        if ( mat [ i + dx [ dir ] ] [ j + dy [ dir ] ] == 1 and  d [ dir ] [ i + dx [ dir ] ] [ j + dy [ dir ] ] > d [ dir ] [ i ] [ j ] )
        {
            d [ dir ] [ i + dx [ dir ] ] [ j + dy [ dir ] ] = d [ dir ] [ i ] [ j ] ;
            Q [ prim ].push ( mp( mp ( i + dx [ dir ] , j + dy [ dir ] ) , dir ) ) ;
        }
        for ( int new_dir = -1 ; new_dir <= 1 ; new_dir += 2 )
            if ( d [ (dir + new_dir + 8 ) % 8 ] [ i ] [ j ] > d [ dir ] [ i ] [ j ] + 1 )
            {
                d [ ( dir + new_dir + 8 ) % 8 ] [ i ] [ j ] = d [ dir ] [ i ] [ j ] + 1 ;
                Q [ secund ].push ( mp( mp ( i , j ) , ( dir + new_dir + 8 ) % 8 ) ) ;
            }
    }
    int sol = INF ;
    for ( int i = 0 ; i < 8 ; ++ i )
        soll ( sol , d [ i ] [ finx ] [ finy ] ) ;
    if ( sol == INF )
        fout << -1 ;
    else fout << sol ;
    return 0;
}