Pagini recente » Cod sursa (job #1436177) | Cei mai harnici utilizatori info-arena | Cod sursa (job #2376096) | Cod sursa (job #3259234) | Cod sursa (job #2536179)
#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],cost;
struct car
{
int l,c;
int d1,d2;
};
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
queue<car> q;
car x,y;
bool isin(int l,int c)
{
if(l<0||l>n||c<0||c>m) return 0;
return 1;
}
void lee(int l,int c)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]=1e9;
d[l][c]=0;
q.push({l,c,0,0});
while(!q.empty())
{
x=q.front();
q.pop();
for(int k=0;k<8;k++)
{
y.l=x.l+dx[k];
y.c=x.c+dy[k];
if(isin(y.l,y.c)&&a[y.l][y.c]==0)
{
if(x.d1==0&&x.d2==0) cost=0;
else cost=abs(x.d1-dx[k])+abs(x.d2-dy[k]);
if(d[x.l][x.c]+cost<d[y.l][y.c])
{
d[y.l][y.c]=d[x.l][x.c]+cost;
q.push({y.l,y.c,dx[k],dy[k]});
}
}
}
}
}
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];
lee(l1,c1);
if(d[l2][c2]!=1e9) out<<d[l2][c2];
else out<<-1;
return 0;
}