Pagini recente » Cod sursa (job #1669155) | Cod sursa (job #1089912) | Cod sursa (job #1922465) | Cod sursa (job #857191) | Cod sursa (job #3239267)
#include <bits/stdc++.h>
using namespace std;
const int dx[]= {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[]= {-1, 0, 1, 1, 1, 0, -1, -1};
int dist[505][505][8], n, m, xs, ys, xf, yf;
bitset<505> a[505];
deque<tuple<int,int,int>> dq;
bool inside(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void bfs()
{
for (int i = 0; i < 8; ++i)
{
dist[xs][ys][i] = 0;
dq.push_back({xs, ys, i});
}
while (!dq.empty())
{
int i, j, dir;
tie(i, j, dir) = dq.front();
dq.pop_front();
int x = i + dx[dir];
int y = j + dy[dir];
if (inside(x, y) && !a[x][y] && dist[x][y][dir] > dist[i][j][dir]) // verificam pt. 0 grade (cost 0)
{
dist[x][y][dir] = dist[i][j][dir];
dq.push_front({x, y, dir});
}
for (int k = -1; k <= 1; k += 2) // ne rotim cu 45 de grade
{
int new_dir = (dir + k + 8) % 8;
if (dist[i][j][new_dir] > dist[i][j][dir] + 1)
{
dist[i][j][new_dir] = dist[i][j][dir] + 1;
dq.push_back({i, j, new_dir});
}
}
}
}
int main()
{
ifstream cin("car.in");
ofstream cout("car.out");
cin >> n >> m >> xs >> ys >> xf >> yf;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
int x;
cin >> x;
a[i][j] = x;
}
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] = INT_MAX;
bfs();
int ans = INT_MAX;
for (int i = 0; i < 8; ++i)
ans = min(ans, dist[xf][yf][i]);
cout << ans;
return 0;
}