Pagini recente » Cod sursa (job #124339) | Cod sursa (job #1024053) | Cod sursa (job #3348968) | Cod sursa (job #3333437) | Cod sursa (job #3312136)
//#pragma GCC optimize("O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int mat[505][505];
int mat2[505][505][8];
int d1[]={-1, -1, 0, 1, 1, 1, 0, -1};
int d2[]={0, 1, 1, 1, 0, -1, -1, -1};
struct stare
{
int fi, se, dir;
};
signed main()
{
ifstream cin("car.in");
ofstream cout("car.out");
int n, m, a1, a2, b1, b2, mincnt=1000000;
cin>>n>>m;
cin>>a1>>b1>>a2>>b2;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>mat[i][j];
for(int k=0; k<=7; k++)
mat2[i][j][k]=1000000;
}
}
queue<stare> q[3];
for(int j=0;j<7;j++)
{
//if(a1+d1[j]>0 && a1+d1[j]<=n && b1+d2[j]>0 && b1+d2[j]<=m && mat[a1+d1[j]][b1+d2[j]]==0)
// {
mat2[a1][b1][j]=0;
q[0].push({a1, b1, j});
//}
}
for(int i=0; i<n*m*4; i++)
{
while(!q[i%3].empty())
{
int x=q[i%3].front().fi, y=q[i%3].front().se, z=q[i%3].front().dir;
q[i%3].pop();
if(x==a2 && y==b2)
{
if(mincnt>i)
mincnt=i;
}
for(int j=-2;j<=2;j++)
{
int xx=z+j;
if(xx<0)
xx+=8;
else if(xx>7)
xx-=8;
if(x+d1[xx]>0 && x+d1[xx]<=n && y+d2[xx]>0 && y+d2[xx]<=m && mat[x+d1[xx]][y+d2[xx]]==0 && mat2[x+d1[xx]][y+d2[xx]][xx]>mat2[x][y][z]+max(j, (-1)*j))
{
mat2[x+d1[xx]][y+d2[xx]][xx]=mat2[x][y][z]+max(j, (-1)*j);
q[(i+max(j, (-1)*j))%3].push({x+d1[xx], y+d2[xx], xx});
}
}
}
}
cout<<mincnt;
return 0;
}