Pagini recente » Cod sursa (job #833239) | Cod sursa (job #1335971) | Cod sursa (job #823712) | Cod sursa (job #2616764) | Cod sursa (job #2132632)
#include <iostream>
#include <fstream>
#include <queue>
#define h i1+i
#define o j1+j
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
struct cr{
short i,j;
}dir[10],aux;
short n,m,i1,j1,i2,j2,d,e,u[505][505],mn,cost;
int a[505][505],inf(1<<30);
queue<cr>q[250005]; bool ok=true;
int directie(int i,int j)
{
for(int r=1;r<=8;++r)
{
if(dir[r].i==i && dir[r].j==j) return r;
}
}
void precalc()
{
///border
for(int i=0;i<=n+1;++i) a[i][0]=a[i][m+1]=-1;
for(int i=0;i<=m+1;++i) a[0][i]=a[n+1][i]=-1;
///directii \ | / 1 2 3
/// - - 8 4
/// / | \ 7 6 5
dir[1].i=dir[2].i=dir[3].i=-1; dir[1].j=-1; dir[3].j=1;
dir[8].j=-1; dir[4].j=1;
dir[6].i=dir[7].i=dir[5].i=1; dir[7].j=-1; dir[5].j=1;
///primele numere in coada
a[i1][j1]=0;
for(int i=-1;i<=1;++i)
{
for(int j=-1;j<=1;++j)
{
d=directie(i,j);
if(a[h][o]==inf)
{
aux.i=h; aux.j=o;
q[0].push(aux);
u[h][o]=d;
a[h][o]=0;
}
}
}
}
int main()
{
f>>n>>m;
f>>i1>>j1>>i2>>j2;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
f>>a[i][j];
if(a[i][j]==1) a[i][j]=-1;
else a[i][j]=inf;
}
}
precalc();
aux=q[0].front();
mn=0;
while(ok==true)
{
ok=false;
while(q[mn].empty()) ++mn;
aux=q[mn].front(); i1=aux.i; j1=aux.j; q[mn].pop();
//cout<<i1<<' '<<j1<<endl;
for(int i=-1;i<=1;++i)
{
for(int j=-1;j<=1;++j)
{
d=directie(i,j); e=u[i1][j1];
cost=d-e; if(cost<0) cost=-cost;
if(cost>4) cost=8-cost;
if(a[h][o]>cost+a[i1][j1])
{
u[h][o]=d;
a[h][o]=cost+a[i1][j1];
aux.i=h; aux.j=o; q[a[h][o]].push(aux);
ok=true;
}
}
}
}
g<<a[i2][j2];
return 0;
}