Pagini recente » Cod sursa (job #38456) | Cod sursa (job #2595306) | Cod sursa (job #685949) | Cod sursa (job #1914157) | Cod sursa (job #2321076)
#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;
priority_queue<pair<pair<int,int>, pair<int,int> > > Q,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())
{
while(Q.size())
{
int cst=-Q.top().first.first;
pair<int,int> x= {Q.top().first.second,Q.top().second.first};
int dir=Q.top().second.second;
Q.pop();
//cout<<x.first<<' '<<x.second<<' '<<dir<<' '<<cst<<'\n';
if(cst>dyn[x.first][x.second][dir])
continue;
if(!a[x.first+dirx[dir]][x.second+diry[dir]])
if(dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]>
dyn[x.first][x.second][dir])
{
dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]=dyn[x.first][x.second][dir];
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;
if(dyn[x.first][x.second][dir]>cst+1)
{
dyn[x.first][x.second][dir]=cst+1;
q.push({{-cst-1,x.first},{x.second,dir}});
}
dir=(dir-2+8)%8;
if(dyn[x.first][x.second][dir]>cst+1)
{
dyn[x.first][x.second][dir]=cst+1;
q.push({{-cst-1,x.first},{x.second,dir}});
}
}
while(q.size())
{
Q.push(q.top());
q.pop();
}
}
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;
}