Pagini recente » Cod sursa (job #402124) | Cod sursa (job #1119150) | Cod sursa (job #2888940) | Cod sursa (job #2883764) | Cod sursa (job #2449964)
#include<cstdio>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
bool a[502][502];
int d[502][502][10];
int dx[]={0,0,1,1,1,0,-1,-1,-1,0};
int dy[]={0,1,1,0,-1,-1,-1,0,1,0};
struct elem
{
int x,y,dir;
};
queue<elem>q0,q1;
elem p;
int main()
{
int n,m,i,j,x1,x2,y1,y2,k,q,sol=2000000000;
f>>n>>m>>x1>>y1>>x2>>y2;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>a[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=1;k<=8;k++)
d[i][j][k]=2000000000;
for(i=0;i<=n+1;i++)
a[i][0]=a[i][m+1]=1;
for(i=0;i<=m+1;i++)
a[0][i]=a[n+1][i]=1;
for(i=1;i<=8;i++)
{
d[x1][y1][i]=0;
if(a[x1][y1]==0)
q0.push(elem{x1,y1,i});
}
while(!q0.empty())
{
while(!q0.empty())
{
p=q0.front();
q0.pop();
if(a[p.x+dx[p.dir]][p.y+dy[p.dir]]==0&&d[p.x+dx[p.dir]][p.y+dy[p.dir]][p.dir]>d[p.x][p.y][p.dir])
{
d[p.x+dx[p.dir]][p.y+dy[p.dir]][p.dir]=d[p.x][p.y][p.dir];
q0.push(elem{p.x+dx[p.dir],p.y+dy[p.dir],p.dir});
}
q=(p.dir+1)%8;
if(a[p.x][p.y]==0&&d[p.x][p.y][q]>d[p.x][p.y][p.dir]+1)
{
d[p.x][p.y][q]=d[p.x][p.y][p.dir]+1;
q1.push(elem{p.x,p.y,q});
}
q=p.dir-1;
if(q==0)
q=8;
if(a[p.x][p.y]==0&&d[p.x][p.y][q]>d[p.x][p.y][p.dir]+1)
{
d[p.x][p.y][q]=d[p.x][p.y][p.dir]+1;
q1.push(elem{p.x,p.y,q});
}
}
while(!q1.empty())
{
q0.push(q1.front());
q1.pop();
}
}
for(i=1;i<=8;i++)
if(d[x2][y2][i]<sol)
sol=d[x2][y2][i];
if(sol==2000000000)
g<<-1;
else
g<<sol;
return 0;
}