Pagini recente » Cod sursa (job #2612609) | Cod sursa (job #1216608) | Cod sursa (job #1330810) | Cod sursa (job #2620113) | Cod sursa (job #2132754)
#include <iostream>
#include <fstream>
#include <queue>
#define h i1+i
#define o j1+j
#define k q[cost][0].i
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
struct cr{
int i,j;
}dir[10],aux,q[5][250005];
int n,m,i1,j1,i2,j2,d,e,u[505][505],cost,b,l,c;
int a[505][505],inf(1<<30);
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
l=i1; c=j1;
a[i1][j1]=0;
aux.i=i1; aux.j=j1;
q[0][0].i=1;
q[0][1]=aux;
}
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][1]; b=0;
while(ok==true)
{
ok=false; cost=0;
while(b==k)
{
cost=1;
while(cost<=4)
{
for(int i=0;i<=k;++i)
{
q[cost-1][i]=q[cost][i];
}
++cost;
}
b=0;
cost=0;
}
++b;
aux=q[0][b]; i1=aux.i; j1=aux.j;
//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(l==i1 && c==j1) cost=0;
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[cost][++k]=aux;
ok=true;
}
}
}
}
g<<a[i2][j2];
return 0;
}