Pagini recente » Cod sursa (job #2275213) | Cod sursa (job #2947443) | Cod sursa (job #3180028) | Cod sursa (job #193524) | Cod sursa (job #2595153)
#include <bits/stdc++.h>
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser fin("car.in");
ofstream fout("car.out");
const int INF = 1e9;
const int DIM = 502;
int harta[DIM][DIM];
int cost[DIM][DIM][8];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
bool vis[DIM][DIM][8];
main()
{
int n, m;
fin >> n >> m;
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
fin >> harta[i][j];
for(int dir = 0; dir < 8; ++dir)
cost[i][j][dir] = INF;
}
for(int i = 0; i <= n + 1; ++i)
harta[i][0] = harta[i][m + 1] = 1;
for(int j = 0; j <= m + 1; ++j)
harta[0][j] = harta[n + 1][j] = 1;
queue <tuple <int, int, int> > q;
for(int dir = 0; dir < 7; ++dir)
{
cost[x1][y1][dir] = 0;
q.push({x1, y1, dir});
vis[x1][y1][dir] = true;
}
while(!q.empty())
{
int x, y, dir;
tie(x, y, dir) = q.front();
q.pop();
vis[x][y][dir] = false;
for(int i = 0; i <= 4; ++i)
{
int ndir = ((dir + i) & 7);
int nx = x + dx[ndir];
int ny = y + dy[ndir];
if(harta[nx][ny] == 0 && cost[nx][ny][ndir] > cost[x][y][dir] + i)
{
cost[nx][ny][ndir] = cost[x][y][dir] + i;
if(vis[nx][ny][ndir] == false)
{
vis[nx][ny][ndir] = true;
q.push({nx, ny, ndir});
}
}
ndir = ((dir - i + 8) & 7);
nx = x + dx[ndir];
ny = y + dy[ndir];
if(harta[nx][ny] == 0 && cost[nx][ny][ndir] > cost[x][y][dir] + i)
{
cost[nx][ny][ndir] = cost[x][y][dir] + i;
if(vis[nx][ny][ndir] == false)
{
vis[nx][ny][ndir] = true;
q.push({nx, ny, ndir});
}
}
}
}
int ans = INF;
for(int dir = 0; dir < 8; ++dir)
ans = min(ans, cost[x2][y2][dir]);
if(ans == INF)
ans = -1;
fout << ans << '\n';
}