Pagini recente » Cod sursa (job #865048) | Cod sursa (job #841275) | Cod sursa (job #2004827) | Cod sursa (job #2853119) | Cod sursa (job #2979321)
/*
"TLE is like the wind, always by my side"
- Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
struct coord
{
short int lin;
short int col;
short int direction;
int cost;
};
queue <coord> q0,q1,q2,qaux;
short int dlin[9] = {1, 1, -1, -1, 1, -1, 0, 0};
short int dcol[9] = {1, -1, 1, -1, 0, 0, 1, -1};
bool a[503][503];
int distans[503][503][9];
bool visited[503][503][9];
int main()
{
ifstream fin("car.in");
ofstream fout("car.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
short int n,m,si,sj,fi,fj,i,j,l,c;
int mi;
coord frontnode;
fin >> n >> m;
fin >> si >> sj >> fi >> fj;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
fin >> a[i][j];
}
}
for (i=0; i<=n+1; i++)
{
a[i][0]=1;
a[i][m+1]=1;
}
for (i=0; i<=m+1; i++)
{
a[0][i]=1;
a[n+1][i]=1;
}
for (i=0; i<8; i++)
{
l=si;
c=sj;
l+=dlin[i];
c+=dcol[i];
if (!a[l][c])
q0.push({l,c,i,0});
}
while (!q0.empty() || !q1.empty() || !q2.empty())
{
while (!q0.empty())
{
frontnode=q0.front();
if (!visited[frontnode.lin][frontnode.col][frontnode.direction])
{
distans[frontnode.lin][frontnode.col][frontnode.direction]=frontnode.cost;
visited[frontnode.lin][frontnode.col][frontnode.direction]=1;
for (i=0; i<8; i++)
{
l=frontnode.lin;
c=frontnode.col;
l+=dlin[i];
c+=dcol[i];
if (!visited[l][c][i] && !a[l][c])
{
if (i==frontnode.direction)
q0.push({l,c,i,frontnode.cost});
else if ((i==0 && (frontnode.direction==4 || frontnode.direction==6)) || (i==1 && (frontnode.direction==7 || frontnode.direction==4)) || (i==2 && (frontnode.direction==6 || frontnode.direction==5)) || (i==3 && (frontnode.direction==5 || frontnode.direction==7)) || (i==4 && (frontnode.direction==0 || frontnode.direction==1)) || (i==5 && (frontnode.direction==2 || frontnode.direction==3)) || (i==6 && (frontnode.direction==0 || frontnode.direction==2)) || (i==7 && (frontnode.direction==1 || frontnode.direction==3)))
q1.push({l,c,i,frontnode.cost+1});
else if (((i==0 || i==3) && (frontnode.direction==1 || frontnode.direction==2)) || ((i==1 || i==2) && (frontnode.direction==0 || frontnode.direction==3)) || ((i==4 || i==5) && (frontnode.direction==6 || frontnode.direction==7)) || ((i==6 || i==7) && (frontnode.direction==4 || frontnode.direction==5)))
q2.push({l,c,i,frontnode.cost+2});
}
}
}
q0.pop();
}
qaux=q2;
q0=q1;
q1=qaux;
while (!q2.empty())
q2.pop();
}
mi=n*m*n;
for (i=0; i<8; i++)
{
if (visited[fi][fj][i])
mi=min(mi,distans[fi][fj][i]);
}
if (mi==(n*m*n))
fout << -1;
else
fout << mi;
}