Pagini recente » Cod sursa (job #3319152) | Cod sursa (job #3314558) | Cod sursa (job #3315231) | Cod sursa (job #3326690) | Cod sursa (job #3346479)
#include <fstream>
#include <queue>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
const int NMAX=5e2+5, INF=1e9;
int n, m, a[NMAX][NMAX], viz[8][NMAX][NMAX], dist[8][NMAX][NMAX];
struct cell{int d, i, j;}s, f;
deque<cell> dq;
int di[8]={1, 1, 0, -1, -1, -1, 0, 1},
dj[8]={0, -1, -1, -1, 0, 1, 1, 1};
int mod(int x)
{
return (x+8)%8;
}
bool valid(cell c)
{
return ((1<=c.i && c.i<=n) && (1<=c.j && c.j<=m) && !a[c.i][c.j]);
}
void check_cell(cell c, cell nc, bool cst)
{
dist[nc.d][nc.i][nc.j]=min(dist[nc.d][nc.i][nc.j], dist[c.d][c.i][c.j]+cst);
if(cst)
dq.push_back(nc);
else
dq.push_front(nc);
}
void BFS01()
{
for(int d=0;d<8;d++)
{
dist[d][s.i][s.j]=0;
dq.push_front({d, s.i, s.j});
}
while(!dq.empty())
{
cell c=dq.front(); dq.pop_front();
if(viz[c.d][c.i][c.j])
continue;
viz[c.d][c.i][c.j]=1;
if(valid({c.d, c.i+di[c.d], c.j+dj[c.d]}))
check_cell(c, {c.d, c.i+di[c.d], c.j+dj[c.d]}, 0);
for(int b=-1;b<=1;b+=2)
check_cell(c, {mod(c.d+b), c.i, c.j}, 1);
}
}
int main()
{
in>>n>>m>>s.i>>s.j>>f.i>>f.j;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
in>>a[i][j];
for(int d=0;d<8;d++)
dist[d][i][j]=INF;
}
BFS01();
int ans=INF;
for(int d=0;d<8;d++)
if(viz[d][f.i][f.j])
ans=min(ans, dist[d][f.i][f.j]);
out<<(ans==INF?-1:ans);
return 0;
}