Pagini recente » Cod sursa (job #2059484) | Cod sursa (job #504485) | Cod sursa (job #2281792) | Cod sursa (job #1042971) | Cod sursa (job #2536751)
#include <bits/stdc++.h>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
int n,m,a[510][510],l1,c1,l2,c2,d[510][510][8],cost,ans,nd;
bool ok[510][510][8];
struct car
{
int l,c;
int d;
};
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
queue<car> q[1500];
car x,y;
bool isin(int l,int c)
{
if(l<=0||l>n||c<=0||c>m) return 0;
return 1;
}
void dial(int l,int c)
{
for(int k=0;k<8;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j][k]=1e9;
for(int k=0;k<8;k++)
{
d[l][c][k]=0;
if(isin(l+dx[k],c+dy[k])&&a[l+dx[k]][c+dy[k]]==0) {
q[0].push({l+dx[k],c+dy[k],k});
d[l+dx[k]][c+dy[k]][k]=0;
}
}
int idx=0;
while(1)
{
int temp=idx;
while(q[idx].size()==0&&idx<2*n)
idx++;
if(idx==2*n) break;
x=q[idx].front();
q[idx].pop();
if(x.l==l2&&x.c==c2)
{
ans=d[l2][c2][x.d];
return;
}
if(ok[x.l][x.c][x.d]==1) continue;
ok[x.l][x.c][x.d]=1;
for(int k=-2;k<=2;k++)
{
if(x.l==l&&x.c==c) cost=0;
else cost=abs(k);
nd=(x.d+k+8)%8;
y.l=x.l+dx[nd];
y.c=x.c+dy[nd];
if(isin(y.l,y.c)&&a[y.l][y.c]==0)
{
if(ok[y.l][y.c][nd]==0&&d[x.l][x.c][x.d]+cost<d[y.l][y.c][nd])
{
d[y.l][y.c][nd]=d[x.l][x.c][x.d]+cost;
q[d[y.l][y.c][nd]].push({y.l,y.c,nd});
}
}
}
}
}
int main()
{
in>>n>>m;
in>>l1>>c1>>l2>>c2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
in>>a[i][j];
ans=1e9;
dial(l1,c1);
if(ans!=1e9) out<<ans;
else out<<-1;
return 0;
}