Pagini recente » Istoria paginii runda/pre___oji___2018 | Cod sursa (job #1938799) | Cod sursa (job #2716994) | Cod sursa (job #2645481) | Cod sursa (job #1232266)
#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;
}