Pagini recente » Cod sursa (job #1813322) | Cod sursa (job #2514129) | Cod sursa (job #377855) | Cod sursa (job #281500) | Cod sursa (job #990954)
Cod sursa(job #990954)
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
const int dl[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
const int Nmax = 505;
const int oo = 0x3f3f3f3f;
const int Cmax = 2;
int A[Nmax][Nmax];
int d[ ( 1 << 21 ) ];
stack <int> Coada[Cmax];
int N, M, x1, y1, x2, y2;
int source, destination;
void read()
{
ifstream f("car.in");
f >> N >> M >> x1 >> y1 >> x2 >> y2;
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
f >> A[i][j],
A[i][j] = 1 - A[i][j];
f.close();
}
inline bool valid( int i, int j )
{
return A[i][j];
}
inline bool expand( int nod )
{
int dir = ( nod >> 18 );
int i = ( nod >> 9 ) & 511;
int j = nod & 511;
int son = ( i << 9 ) + j + ( ( ( dir + 1 ) % 8 ) << 18 );
if ( d[son] > d[nod] + 1 )
{
d[son] = d[nod] + 1;
Coada[ d[son] % 2 ].push( son );
}
son = ( i << 9 ) + j + ( ( ( dir - 1 + 8 ) % 8 ) << 18 );
if ( d[son] > d[nod] + 1 )
{
d[son] = d[nod] + 1;
Coada[ d[son] % 2 ].push( son );
}
i += dl[dir];
j += dc[dir];
if ( !valid( i, j ) )
return false;
if ( i == x2 && j == y2 )
return true;
son = ( i << 9 ) + j + ( dir << 18 );
if ( d[son] > d[nod] )
{
d[son] = d[nod];
Coada[ d[son] % 2 ].push( son );
}
return false;
}
int Dijkstra()
{
memset( d, oo, sizeof( d ) );
for ( int k = 0; k < 8; ++k )
{
int source = ( x1 << 9 ) + y1 + ( k << 18 );
Coada[0].push( source );
d[source] = 0;
}
int solution = 0;
while( Coada[0].size() + Coada[1].size() > 0 )
{
while( Coada[ solution % 2 ].size() )
{
int nod = Coada[ solution % 2 ].top();
Coada[ solution % 2 ].pop();
if ( expand( nod ) )
{
return solution;
}
}
solution++;
}
return -1;
}
void print()
{
ofstream g("car.out");
g << Dijkstra() << "\n";
g.close();
}
int main()
{
read();
print();
return 0;
}