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