Pagini recente » Cod sursa (job #1108176) | Cod sursa (job #3277162) | Cod sursa (job #543294) | Cod sursa (job #969217) | Cod sursa (job #2497508)
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f ("car.in");
ofstream g ("car.out");
int n,m;
int startx, starty, stopx, stopy;
int mak[501][501];
int cost[501][501][4][4];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
struct Dir{
int dirx;
int diry;
};
struct Nod{
int x;
int y;
Dir commingdir;
int val;
};
//queue < Nod> coada;
Nod heap[500004];
int nn;
Nod getMin()
{
return heap[1];
}
void add(Nod x)
{
nn++;
int poz=nn;
heap[nn]=x;
while(poz>1 && heap[poz/2].val>heap[poz].val)
{
swap(heap[poz/2], heap[poz]);
poz/=2;
}
}
int popMin()
{
heap[1]=heap[nn];
heap[nn]={0,0,{0,0},0};
int poz=1;
nn--;
while(2*poz<=nn)
{
poz*=2;
if(poz<nn && heap[poz].val>heap[poz+1].val) poz++;
if(heap[poz].val < heap[poz/2].val)
swap(heap[poz/2], heap[poz]);
else poz=nn;
}
}
bool isok(int x, int y)
{
if(1<=x && x<=n && 1<=y && y<=m)
return true;
return false;
}
void lee()
{
//coada.push({startx,starty,{0, 0}});
add({startx,starty,{0, 0}});
Nod elem={startx, starty};
int inext, jnext;
while(nn>0)
{
elem=getMin();
int icurent = elem.x;
int jcurent = elem.y;
Dir dirr=elem.commingdir;
popMin();
Nod child;
Dir d;
if(dirr.dirx==0 && dirr.diry==0)
{
for(int dd=0;dd<8;++dd)
{
inext=icurent+dx[dd];
jnext=jcurent+dy[dd];
if(isok(inext, jnext))
{
if(icurent==startx && jcurent==starty && mak[inext][jnext]==0)
{
// mak[inext][jnext]=mak[icurent][jcurent];
child.x=inext;
child.y=jnext;
d.dirx=inext-startx;
d.diry=-(jnext-starty);
child.commingdir=d;
cost[inext][jnext][d.dirx+1][d.diry+1]=0;
child.val=0;
add(child);
}
}
}
} else {
for(int dd=0;dd<8;++dd)
{
inext=icurent+dx[dd];
jnext=jcurent+dy[dd];
if(isok(inext, jnext) && mak[inext][jnext]==0)
{
//cout<<"k";
child.x=inext;
child.y=jnext;
d.dirx=inext-icurent;
d.diry=-(jnext-jcurent);
Dir cdir;
cdir.dirx=2*(d.dirx*dirr.dirx+d.diry*dirr.diry)/(dirr.dirx*dirr.dirx+dirr.diry*dirr.diry);
cdir.diry=2*(d.diry*dirr.dirx - d.dirx*dirr.diry)/(dirr.dirx*dirr.dirx+dirr.diry*dirr.diry);
if(abs(cdir.dirx)==2 )
{
cdir.dirx/=2;
cdir.diry/=2;
} else if(abs(cdir.diry)==2 )
{
cdir.dirx/=2;
cdir.diry/=2;
}
child.commingdir=d;
if(cdir.dirx==1&& cdir.diry==0 &&
(cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]) )
cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1] , child.val=0, add(child) ;
else if(cdir.dirx==1&& abs(cdir.diry)==1 &&
(cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+1 ))
cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+1 , child.val=1, add(child);
else if(cdir.dirx==0&& abs(cdir.diry)==1 &&
(cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+2))
cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+2 , child.val=2, add(child);
}
}
}
}
}
int main()
{
f>>n>>m>>startx>>starty>>stopx>>stopy;
// if(mak[startx][starty]==-1)
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cost[i][j][0][0]=1e9;
cost[i][j][0][1]=1e9;
cost[i][j][0][2]=1e9;
cost[i][j][1][0]=1e9;
cost[i][j][1][1]=1e9;
cost[i][j][1][2]=1e9;
cost[i][j][2][0]=1e9;
cost[i][j][2][1]=1e9;
cost[i][j][2][2]=1e9;
f>>mak[i][j];
}
}
if(mak[startx][starty]==1 || mak[stopx][stopy] == 1)
{
g<<"-1";
return 0;
}
cost[startx][starty][0][0]=0;
cost[startx][starty][0][1]=0;
cost[startx][starty][0][2]=0;
cost[startx][starty][1][0]=0;
cost[startx][starty][1][1]=0;
cost[startx][starty][1][2]=0;
cost[startx][starty][2][0]=0;
cost[startx][starty][2][1]=0;
cost[startx][starty][2][2]=0;
lee();
int mi=1e9;
for(int di=0;di<3;++di)
{
for(int dj=0;dj<3;++dj)
{
//g<<cost[stopx][stopy][di][dj]<<" ";
// if(cost[stopx][stopy][di][dj]!=0)
mi=min(cost[stopx][stopy][di][dj],mi);
}
// g<<"\n";
}
if(mi==1e9)
mi=-1;
g<<mi;
return 0;
}