Pagini recente » Cod sursa (job #3039850) | Cod sursa (job #556010) | Cod sursa (job #2545278) | Cod sursa (job #2803933) | Cod sursa (job #2724157)
#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 500
#define f first
#define s second
#define inf 2000000000
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int n, m, cost[NMAX+10][NMAX+10][8];
bool v[NMAX+10][NMAX+10], viz[NMAX+10][NMAX+10][8];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
pair <int, int> p1, p2;
queue <pair <pair <int, int>, int > > Q[5];
int main()
{
fin >> n >> m >> p1.f >> p1.s >> p2.f >> p2.s;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
fin >> v[i][j];
if(v[p1.f][p1.s] || v[p2.f][p2.s])
{ fout << -1 << '\n';
return 0;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int t=0; t<8; t++)
cost[i][j][t] = inf;
int curr = 0;
for(int t=0; t<8; t++)
{ Q[0].push({p1, t});
cost[p1.f][p1.s][t] = 0;
}
while(Q[0].size() || Q[1].size() || Q[2].size() || Q[3].size() || Q[4].size())
{ while(Q[curr].empty())
{ curr++;
if(curr == 5)
curr = 0;
}
pair <pair <int, int>, int > a = Q[curr].front();
Q[curr].pop();
int r = a.f.f, c = a.f.s, dir = a.s;
if(viz[r][c][dir])
continue;
viz[r][c][dir] = 1;
if(r == p2.f && c == p2.s)
{ fout << cost[r][c][dir] << '\n';
return 0;
}
for(int t=1; t<=4; t++)
{ int newdir = (dir + t) % 8;
if(t + cost[r][c][dir] < cost[r][c][newdir])
{ cost[r][c][newdir] = cost[r][c][dir] + t;
Q[(curr+t)%5].push({{r, c}, newdir});
}
newdir = (dir - t + 8) % 8;
if(t + cost[r][c][dir] < cost[r][c][newdir])
{ cost[r][c][newdir] = cost[r][c][dir] + t;
Q[(curr+t)%5].push({{r, c}, newdir});
}
}
pair <int, int> vec = {dx[dir] + r, dy[dir] + c};
if(vec.f && vec.s && vec.f <= n && vec.s <= m && !v[vec.f][vec.s] && cost[r][c][dir] < cost[vec.f][vec.s][dir])
{ cost[vec.f][vec.s][dir] = cost[r][c][dir];
Q[curr].push({vec, dir});
}
}
fout << -1 << '\n';
return 0;
}