Pagini recente » Cod sursa (job #51669) | Cod sursa (job #3172945) | Cod sursa (job #751306) | Cod sursa (job #1982353) | Cod sursa (job #1703418)
#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;
}