Pagini recente » Cod sursa (job #3121564) | Cod sursa (job #3285675) | Cod sursa (job #2222388) | Cod sursa (job #2388912) | Cod sursa (job #3276628)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int dx[]= {-1,-1,0,1,1,1,0,-1};
const int dy[]= {0,1,1,1,0,-1,-1,-1};
const int Nmax=505;
bool a[Nmax][Nmax];
bool viz[Nmax][Nmax][10];
int d[Nmax][Nmax][10];
bool inq[Nmax][Nmax][10];
struct celula
{
short int x,y;
short int dir;
};
int n,m;
bool inmat(int i,int j)
{
return (1<=i && i<=n && 1<=j && j<=m);
}
int main()
{
fin>>n>>m;
int sx,sy,fx,fy;
fin>>sx>>sy>>fx>>fy;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
fin>>a[i][j];
for(int k=0;k<8;k++) d[i][j][k]=-1;
}
}
queue<celula> q;
for(int k=0;k<8;k++)
{
q.push({sx,sy,k});
d[sx][sy][k]=0;
}
while(!q.empty())
{
int i=q.front().x;
int j=q.front().y;
int dr=q.front().dir;
int cost=d[i][j][dr];
q.pop();
inq[i][j][dr]=0;
int newi=i+dx[dr],newj=j+dy[dr];
if(inmat(newi,newj) && a[i][j]!=1)
{
if(d[newi][newj][dr]==-1 || d[newi][newj][dr]>cost)
{
d[newi][newj][dr]=cost;
if(!inq[newi][newj][dr])
{
q.push({newi,newj,dr});
inq[newi][newj][dr]=1;
}
}
}
for(int turn=1;turn<=4;turn++)
{
int k=(dr+turn)%8;
if(d[i][j][k]==-1 || d[i][j][k]>cost+turn)
{
d[i][j][k]=cost+turn;
if(!inq[i][j][k])
{
q.push({i,j,k});
inq[i][j][k]=1;
}
}
if(turn==4) continue;
k=(dr+8-turn)%8;
if(d[i][j][k]==-1 || d[i][j][k]>cost+turn)
{
d[i][j][k]=cost+turn;
if(!inq[i][j][k])
{
q.push({i,j,k});
inq[i][j][k]=1;
}
}
}
}
int ans=INT_MAX;
for(int k=0;k<8;k++) if(d[fx][fy][k]!=-1) ans=min(ans,d[fx][fy][k]);
fout<<ans<<'\n';
return 0;
}