Pagini recente » Cod sursa (job #373911) | Cod sursa (job #2047402) | Cod sursa (job #2878) | Cod sursa (job #2814189) | Cod sursa (job #2206719)
#include<fstream>
#include<queue>
using namespace std;
ifstream fi("car.in");
ofstream fo("car.out");
int n,m,x,y,xx,yy,k,i,j,D[8][505][505],nd,A[505][505],c;
pair<int,pair<int,int> > val;
deque<pair<int,pair<int,int> > > Q[3];
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int modul(int x)
{
if(x<0)
return -x;
return x;
}
int main()
{
fi>>n>>m;
fi>>x>>y>>xx>>yy;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
fi>>A[i][j];
for(k=0; k<8; k++)
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
D[k][i][j]=1000000000;
for(i=0; i<8; i++)
{
D[i][x][y]=0;
Q[0].push_back({i,{x,y}});
}
for(i=0; i<=500000; i++)
{
while(!Q[i%3].empty())
{
val=Q[i%3].front();
Q[i%3].pop_front();
if(i>D[val.first][val.second.first][val.second.second])
continue;
if(val.second.first==xx && val.second.second==yy)
{
fo<<D[val.first][val.second.first][val.second.second]<<"\n";
fi.close();
fo.close();
return 0;
}
for(j=-1; j<=1; j++)
{
c=modul(j);
nd=(val.first+j+8)%8;
if(A[val.second.first+dx[nd]][val.second.second+dy[nd]]==0 && val.second.second+dy[nd]>=1 && val.second.second+dy[nd]<=m && val.second.first+dx[nd]>=1 && val.second.first+dx[nd]<=n && D[nd][val.second.first+dx[nd]][val.second.second+dy[nd]]>i+c)
{
D[nd][val.second.first+dx[nd]][val.second.second+dy[nd]]=i+c;
Q[(i+c)%3].push_back({nd,{val.second.first+dx[nd],val.second.second+dy[nd]}});
}
}
}
}
fo<<"-1\n";
fi.close();
fo.close();
return 0;
}