Pagini recente » Cod sursa (job #2094696) | Cod sursa (job #2142789) | Cod sursa (job #502595) | Cod sursa (job #1251058) | Cod sursa (job #2875970)
#include <bits/stdc++.h>
using namespace std;
ifstream r("car.in");
ofstream w("car.out");
const int inf = 0x3f3f3f3f;
struct poz
{
int i, j, dir, cost;
};
queue<poz>q0, q1;
int n, m, a, b, c, d, dp[503][503][10], l[]={-1, -1, 0, 1, 1, 1, 0, -1}, col[]={0, 1, 1, 1, 0, -1, -1, -1};
bool mat[503][503];
bool ver(int x, int y)
{
return 0<x&&0<y&&x<=n&&y<=m&&!mat[x][y];
}
void bfs()
{
poz nod, urm;
while(q0.size()!=0)
{
while(q0.size()!=0)
{
nod = q0.front();
q0.pop();
urm.i = nod.i + l[nod.dir];
urm.j = nod.j + col[nod.dir];
urm.dir = nod.dir, urm.cost = nod.cost;
if (ver(urm.i, urm.j) && dp[urm.i][urm.j][urm.dir] > urm.cost)
{
dp[urm.i][urm.j][urm.dir] = urm.cost;
q0.push(urm);
}
urm.cost++;
urm.dir = (urm.dir + 1) % 8;
urm.i = nod.i;
urm.j = nod.j;
if (ver(urm.i, urm.j) && dp[urm.i][urm.j][urm.dir] > urm.cost)
{
dp[urm.i][urm.j][urm.dir] = urm.cost;
q1.push(urm);
}
urm.dir = nod.dir - 1;
if (urm.dir < 0)
{
urm.dir = 7;
}
if (ver(urm.i, urm.j) && dp[urm.i][urm.j][urm.dir] > urm.cost)
{
dp[urm.i][urm.j][urm.dir] = urm.cost;
q1.push(urm);
}
}
while(!q1.empty())
{
q0.push(q1.front());
q1.pop();
}
}
}
int main()
{
r>>n>>m>>a>>b>>c>>d;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
r>>mat[i][j];
for(int k = 0; k < 8; k++)
{
dp[i][j][k] = inf;
}
}
}
for(int i = 0; i < 8; i++)
{
q0.push({a, b, i, 0});
}
bfs();
int ans = inf;
for(int i = 0; i < 8; i++)
{
ans = min(ans, dp[c][d][i]);
}
if(ans == inf)
{
w<<-1;
}
else
{
w<<ans;
}
return 0;
}