Pagini recente » Cod sursa (job #3191022) | Cod sursa (job #3209511) | Cod sursa (job #537506) | Cod sursa (job #623672) | Cod sursa (job #2837011)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int maxN = 505, inf = 0x3f3f3f3f;
int dlin[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dcol[] = {0, 1, 1, 1, 0, -1, -1, -1};
struct pozitie{
int i, j, dir, cost;
};
queue <pozitie> q0, q1;
int n, m, x1, y1, x2, y2, dp[maxN][maxN][10];
bool mat[maxN][maxN];
bool InBounds(int x, int y)
{
return 0 < x && 0 < y && x <= n && y <= m && !mat[x][y];
}
void citire()
{
fin >> n >> m >> x1 >> y1 >> x2 >> y2;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
fin >> mat[i][j];
for(int k = 0; k < 8; k++)
dp[i][j][k] = inf;
}
}
for(int i = 0; i < 8; i++)
q0.push({x1, y1, i, 0});
}
void bfs()
{
pozitie nod, vecin;
while(!q0.empty())
{
while(!q0.empty())
{
nod = q0.front();
q0.pop();
vecin.i = nod.i + dlin[nod.dir];
vecin.j = nod.j + dcol[nod.dir];
vecin.dir = nod.dir, vecin.cost = nod.cost;
if (InBounds(vecin.i, vecin.j) && dp[vecin.i][vecin.j][vecin.dir] > vecin.cost)
{
dp[vecin.i][vecin.j][vecin.dir] = vecin.cost;
q0.push(vecin);
}
vecin.cost++;
vecin.dir = (vecin.dir + 1) % 8;
vecin.i = nod.i;
vecin.j = nod.j;
if (InBounds(vecin.i, vecin.j) && dp[vecin.i][vecin.j][vecin.dir] > vecin.cost)
{
dp[vecin.i][vecin.j][vecin.dir] = vecin.cost;
q1.push(vecin);
}
vecin.dir = nod.dir - 1;
if (vecin.dir < 0)
vecin.dir = 7;
if (InBounds(vecin.i, vecin.j) && dp[vecin.i][vecin.j][vecin.dir] > vecin.cost)
{
dp[vecin.i][vecin.j][vecin.dir] = vecin.cost;
q1.push(vecin);
}
}
while(!q1.empty())
{
q0.push(q1.front());
q1.pop();
}
}
}
void afis()
{
int ans = inf;
for(int i = 0; i < 8; i++)
ans = min(ans, dp[x2][y2][i]);
if(ans == inf)
fout << -1;
else
fout << ans;
}
int main()
{
citire();
bfs();
afis();
return 0;
}