Pagini recente » Cod sursa (job #36082) | Cod sursa (job #2137078) | Cod sursa (job #53635) | Cod sursa (job #636983) | Cod sursa (job #2849282)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define punct pair<int,int>
#define x first
#define y second
#define mp make_pair
#define nl '\n'
using namespace std;
ifstream f ( "car.in" );
ofstream g ( "car.out" );
const int NMAX = 503, INF = 1e9;
bool m[NMAX][NMAX];
int cost[NMAX][NMAX][8];
int N, M;
punct init, fin;
punct d[8] = {mp ( 1, 1 ), mp ( 1, 0 ), mp ( 1, -1 ), mp ( 0, -1 ), mp ( -1, -1 ), mp ( -1, 0 ), mp ( -1, 1 ) };
void bordare()
{
for ( int i = 0; i <= N + 1; i++ )
m[i][0] = m[i][M + 1] = 1;
for ( int j = 0; j <= M + 1; j++ )
m[0][j] = m[N + 1][j] = 1;
}
struct incotro
{
punct p;
int dir;
};
void initCost()
{
for ( int i = 1; i <= N; i++ )
for ( int j = 1; j <= M; j++ )
for ( int dir = 0; dir < 8; dir++ )
cost[i][j][dir] = INF;
}
void Lee ( punct init )
{
queue<incotro>Q;
for ( int i = 0; i < 8; i++ )
{
Q.push ( {init, i} );
cost[init.x][init.y][i] = 0;
}
while ( !Q.empty() )
{
punct crt = Q.front().p;
int dircrt = Q.front().dir;
Q.pop();
for ( int i = 0; i < 8; i++ )
{
punct vec;
vec.x = crt.x + d[i].x;
vec.y = crt.y + d[i].y;
if ( m[vec.x][vec.y] == 1 )
continue;
int difabs = abs ( dircrt - i );
int costcrt = cost[crt.x][crt.y][dircrt];
if ( difabs == 0 ) ///cost 0
{
if ( cost[vec.x][vec.y][i] > costcrt )
{
cost[vec.x][vec.y][i] = costcrt;
Q.push ( {vec, i} );
}
}
else
if ( difabs == 1 || difabs == 7 ) ///cost 1
{
if ( costcrt + 1 < cost[vec.x][vec.y][i] )
{
cost[vec.x][vec.y][i] = costcrt + 1;
Q.push ( {vec, i} );
}
}
else
if ( difabs == 2 || difabs == 6 ) ///cost 2
{
if ( costcrt + 2 < cost[vec.x][vec.y][i] )
{
cost[vec.x][vec.y][i] = costcrt + 2;
Q.push ( {vec, i} );
}
}
else
if ( difabs == 3 || difabs == 5 ) ///cost 3
{
if ( costcrt + 3 < cost[vec.x][vec.y][i] )
{
cost[vec.x][vec.y][i] = costcrt + 3;
Q.push ( {vec, i} );
}
}
else
if ( costcrt + 4 < cost[vec.x][vec.y][i] )
{
cost[vec.x][vec.y][i] = costcrt + 4;
Q.push ( {vec, i} );
}
}
}
}
int main()
{
f >> N >> M;
f >> init.x >> init.y >> fin.x >> fin.y;
for ( int i = 1; i <= N; i++ )
for ( int j = 1; j <= M; j++ )
f >> m[i][j];
bordare();
initCost();
Lee ( init );
int ans = INF;
for ( int i = 0; i < 8; i++ )
ans = min ( ans, cost[fin.x][fin.y][i] );
g << ans;
return 0;
}