Pagini recente » Cod sursa (job #5824) | Cod sursa (job #3238252) | Cod sursa (job #817908) | Cod sursa (job #649054) | Cod sursa (job #2537717)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int nmax = 505;
int n, m;
int sx, sy, fx, fy;
struct el
{
int x, y, c, dir;
};
int mat[nmax][nmax];
int dist[nmax][nmax][10];
queue <el> c1, c2;
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
inline void read()
{
fin >> n >> m;
fin >> sx >> sy >> fx >> fy;
int i, j;
for (i = 1; i <= n; i++)
for (j = 1; j <= m;j++)
{
fin >> mat[i][j];
for (int k = 0; k <= 8; k++)
dist[i][j][k] = 2e9;
}
}
inline bool ok(el b)
{
return (b.x >= 1 && b.x <= n && b.y <= m && b.x >= 1 && mat[b.x][b.y] == 0);
}
inline void bfs()
{
el a, b;
for (int i = 0; i < 8; i++)
c1.push({sx, sy, 0, i});
while (!c1.empty())
{
while (!c1.empty())
{
a = c1.front();
c1.pop();
b.x = a.x + dx[a.dir];
b.y = a.y + dy[a.dir];
b.c = a.c;
b.dir = a.dir;
if (ok(b) && dist[b.x][b.y][b.dir] > b.c)
{
dist[b.x][b.y][b.dir] = b.c;
c1.push(b);
}
b.x = a.x;
b.y = a.y;
b.c = a.c + 1;
b.dir = b.dir + 1;
if (b.dir > 7)
b.dir = 0;
if (ok(b) && dist[b.x][b.y][b.dir] > b.c)
{
dist[b.x][b.y][b.dir] = b.c;
c2.push(b);
}
b.dir = a.dir - 1;
if (b.dir < 0)
b.dir = 7;
if (ok(b) && dist[b.x][b.y][b.dir] > b.c)
{
dist[b.x][b.y][b.dir] = b.c;
c2.push(b);
}
}
while (!c2.empty())
{
c1.push(c2.front());
c2.pop();
}
}
int ans = 2e9;
for (int i = 0; i < 8; i++)
ans = min(ans, dist[fx][fy][i]);
fout << ans;
}
int main()
{
read();
bfs();
return 0;
}