Pagini recente » Cod sursa (job #1444651) | Cod sursa (job #2875168) | Cod sursa (job #393987) | Cod sursa (job #1642998) | Cod sursa (job #2494768)
#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;
};
queue < Nod> coada;
bool isok(int x, int y)
{
if(1<=x && x<=n && 1<=y && y<=m)
return true;
return false;
}
void lee()
{
// mak[startx][startx] = 1;
coada.push({startx,starty,{0, 0}});
//coada.push2(make_pair(startx,starty));
Nod elem={startx, starty};
int inext, jnext;
while(!coada.empty())
{
elem=coada.front();
int icurent = coada.front().x;
int jcurent = coada.front().y;
Dir dirr=elem.commingdir;
// cout<<dirr.dirx<<" "<<dirr.diry<<"\n";
//viz[icurent][jcurent]=1;
coada.pop();
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];
Nod child;
child.x=inext;
child.y=jnext;
Dir d;
d.dirx=inext-startx;
d.diry=-(jnext-starty);
child.commingdir=d;
cost[inext][jnext][d.dirx+1][d.diry+1]=0;
coada.push(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";
Nod child;
child.x=inext;
child.y=jnext;
Dir d;
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;
}
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]+0 ) )
cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+0 , coada.push(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 , coada.push(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 , coada.push(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]+3))
cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+3 , coada.push(child);
else if(cdir.dirx==-1&& abs(cdir.diry)==0 &&
(cost[inext][jnext][d.dirx+1][d.diry+1]>cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+4))
cost[inext][jnext][d.dirx+1][d.diry+1]=cost[icurent][jcurent][elem.commingdir.dirx+1][elem.commingdir.diry+1]+4 , coada.push(child);
}
}
}
}
}
int main()
{
f>>n>>m>>startx>>starty>>stopx>>stopy;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
f>>mak[i][j];
if(mak[i][j]==1)
mak[i][j]=-1;
}
}
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;
}