Pagini recente » Cod sursa (job #932662) | Cod sursa (job #897862) | Cod sursa (job #2299608) | Cod sursa (job #1400351) | Cod sursa (job #3235863)
#include <bits/stdc++.h>
std :: ifstream in ("car.in");
std :: ofstream out ("car.out");
const int NMAX = 5e2 + 5;
const int INF = 2e9;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n;
int m;
int xs;
int ys;
int xf;
int yf;
int mini = INF;
bool a[NMAX][NMAX];
bool visited[NMAX][NMAX][8];
int dist[NMAX][NMAX][8];
std :: deque <std :: pair<std :: pair<int, int>, int>> dq;
inline bool inbound(int i, int j)
{
return i >= 1 && j >= 1 && i <= n && j <= m;
}
void bfs()
{
while(!dq.empty())
{
int x = dq.front().first.first;
int y = dq.front().first.second;
int dir = dq.front().second;
dq.pop_front();
if(visited[x][y][dir] == false)
{
visited[x][y][dir] = true;
if(inbound(x + dx[dir], y + dy[dir]) && visited[x + dx[dir]][y + dy[dir]][dir] == false && a[x + dx[dir]][y + dy[dir]] == false && dist[x][y][dir] < dist[x + dx[dir]][y + dy[dir]][dir])
{
dq.push_front(std :: make_pair(std :: make_pair(x + dx[dir], y + dy[dir]), dir));
dist[x + dx[dir]][y + dy[dir]][dir] = dist[x][y][dir];
}
int ac_dir = dir + 1;
ac_dir %= 8;
if(visited[x][y][ac_dir] == false && dist[x][y][dir] + 1 < dist[x][y][ac_dir])
{
dq.push_back(std :: make_pair(std :: make_pair(x, y), ac_dir));
dist[x][y][ac_dir] = dist[x][y][dir] + 1;
}
ac_dir = dir - 1;
if(ac_dir < 0)
{
ac_dir += 8;
}
if(visited[x][y][ac_dir] == false && dist[x][y][dir] + 1 < dist[x][y][ac_dir])
{
dq.push_back(std :: make_pair(std :: make_pair(x, y), ac_dir));
dist[x][y][ac_dir] = dist[x][y][dir] + 1;
}
}
}
}
int main()
{
in >> n >> m;
in >> xs >> ys >> xf >> yf;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
in >> a[i][j];
}
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
for(int k = 0; k < 8; k ++)
{
dist[i][j][k] = INF;
}
}
}
for(int i = 0; i < 8; i ++)
{
dq.push_front(std :: make_pair(std :: make_pair(xs, ys), i));
dist[xs][ys][i] = 0;
}
bfs();
for(int i = 0; i <8; i ++)
{
mini = std :: min(mini, dist[xf][yf][i]);
}
if(mini == INF)
{
out << -1;
}
else
{
out << mini;
}
return 0;
}