Pagini recente » Cod sursa (job #1716166) | Cod sursa (job #841556) | Cod sursa (job #982756) | Cod sursa (job #2293556) | Cod sursa (job #2321046)
#include <bits/stdc++.h>>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int n,m,i,j,dirx[10],diry[10],a[510][510],dyn[510][510][10];
pair<int,int> in,out;
queue<pair<pair<int,int>, pair<int,int> > > Q;
int main()
{
f>>n>>m>>in.first>>in.second>>out.first>>out.second;
dirx[0]=-1;
diry[0]= 0;
dirx[1]=-1;
diry[1]= 1;
dirx[2]= 0;
diry[2]= 1;
dirx[3]= 1;
diry[3]= 1;
dirx[4]= 1;
diry[4]= 0;
dirx[5]= 1;
diry[5]=-1;
dirx[6]= 0;
diry[6]=-1;
dirx[7]=-1;
diry[7]=-1;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
f>>a[i][j];
for(i=0; i<=n+1; i++)
a[i][0]=a[i][m+1]=1;
for(j=0; j<=m+1; j++)
a[0][j]=a[n+1][j]=1;
memset(dyn,127,sizeof(dyn));
for(i=0; i<8; i++)
{
Q.push({{0,in.first},{in.second,i}});
dyn[in.first][in.second][i]=0;
}
while(Q.size())
{
int cst=-Q.front().first.first;
pair<int,int> x= {Q.front().first.second,Q.front().second.first};
int dir=Q.front().second.second;
Q.pop();
if(cst>dyn[x.first][x.second][dir])
continue;
int val=0;
for(i=0; i<=4; i++)
{
if(!a[x.first+dirx[dir]][x.second+diry[dir]])
if(dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]>cst+val)
{
dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]=cst+val;
Q.push({{-dyn[x.first+dirx[dir]][x.second+diry[dir]][dir],x.first+dirx[dir]},{x.second+diry[dir],dir}});
}
dir=(dir+1)%8;
val++;
}
val-=2;
for(i=0; i<=2; i++)
{
if(!a[x.first+dirx[dir]][x.second+diry[dir]])
if(dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]>cst+val)
{
dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]=cst+val;
Q.push({{-dyn[x.first+dirx[dir]][x.second+diry[dir]][dir],x.first+dirx[dir]},{x.second+diry[dir],dir}});
}
dir=(dir+1)%8;
val--;
}
}
int ans=1e9;
for(i=0; i<=7; i++)
ans=min(ans,dyn[out.first][out.second][i]);
if(ans!=1e9)
g<<ans;
else
g<<-1;
return 0;
}