Pagini recente » Cod sursa (job #466065) | Cod sursa (job #2999928) | Cod sursa (job #2459059) | Cod sursa (job #3284374) | Cod sursa (job #3276613)
#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;
q.push({sx,sy,-1});
if(a[sx][sy]==1)
{
cout<<-1<<'\n';
return 0;
}
while(!q.empty())
{
int i=q.front().x;
int j=q.front().y;
int dr=q.front().dir;
int cost;
if(dr!=-1) cost=d[i][j][dr];
else cost=0;
q.pop();
inq[i][j][dr]=0;
///cout<<i<<' '<<j<<' '<<dr<<' '<<cost<<'\n';
for(int k=0; k<8; k++)
{
int newi=i+dx[k];
int newj=j+dy[k];
if(!inmat[newi][newj] || a[newi][newj]==1) continue;
///cout<<newi<<' '<<newj<<' '<<d[newi][newj][k]<<'\n';
int turn;
/// 0 degree "turn"
if(abs(k-dr)==0 || dr==-1) turn=0;
/// 45 degree turn
else if(abs(k-dr)==1 || abs(k-dr)==7) turn=1;
///90 degree turn
else if(abs(k-dr)==2 || abs(k-dr)==6) turn=2;
/// 135 degree turn
else if(abs(k-dr)==3 || abs(k-dr)==5) turn=3;
///180 degree turn
else if(abs(k-dr)==4) turn=4;
if(d[newi][newj][k]==-1 || d[newi][newj][k]>cost+turn)
{
d[newi][newj][k]=cost+turn;
if(!inq[newi][newj][k])
{
q.push({newi,newj,k});
inq[newi][newj][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;
}