Pagini recente » Cod sursa (job #2150858) | Cod sursa (job #1153033) | runda/suceavaftw | Cod sursa (job #1081274) | Cod sursa (job #1096079)
#include <fstream>
#include <iostream>
#include <queue>
#include <cstring>
#define NMax 512
#define MMax 512
using namespace std;
const int INF = 0x3f3f3f3f;
bool foundSol = false;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m;
int a[NMax][MMax], dist[8][NMax][MMax];
struct stare
{
int x, y, dir;
stare() {}
stare(const int _x, const int _y, const int _dir)
{
x = _x, y = _y, dir = _dir;
}
};
queue <stare> Q[2];
int xs, ys, xf, yf;
void Read()
{
ifstream f("car.in");
f>>n>>m>>xs>>ys>>xf>>yf;
for (int i = 1; i<=n; ++i)
for (int j = 1; j<=m; ++j)
f>>a[i][j];
f.close();
}
void Bordare()
{
int n1 = n + 1, m1 = m + 1;
for (int i = 0; i<=n1; ++i)
a[i][0] = a[i][m1] = 1;
for (int i = 0; i<=m1; ++i)
a[0][i] = a[n1][i] = 1;
}
void Solve()
{
Bordare();
memset(dist, INF, sizeof(dist));
for (int i = 0 ; i < 8 ; ++i)
{
if (a[xs + dx[i]][ys + dy[i]] == 0)
{
dist[i][xs + dx[i]][ys + dy[i]] = 0;
Q[0].push(stare(xs + dx[i], ys + dy[i], i));
/// pun coordonatele unde ajung imediat din start + directia din care vin
}
}
int p = 0;
while (!Q[p].empty())
{
while (!Q[p].empty())
{
stare aux = Q[p].front(); Q[p].pop();
if (aux.x == xf && aux.y == yf)
{
ofstream g("car.out");
g<<dist[aux.dir][xf][yf]<<"\n";
g.close();
foundSol = true;
return ;
}
int nowdir = aux.dir, nextdir, cost;
/// ma duc mai departe pe aceeasi directie cu cost 0
cost = 0; nextdir = nowdir;
if (a[aux.x + dx[nextdir]][aux.y + dy[nextdir]] == 0 && dist[nowdir][aux.x][aux.y] + cost < dist[nextdir][aux.x + dx[nextdir]][aux.y + dy[nextdir]])
{
dist[nextdir][aux.x + dx[nextdir]][aux.y + dy[nextdir]] = dist[nowdir][aux.x][aux.y] + cost;
Q[p].push(stare(aux.x + dx[nextdir], aux.y + dy[nextdir], nextdir));
}
/// raman aici dar schimb directia la 45 de grade intr-o parte cu cost 1
cost = 1, nextdir = nowdir + 1 >= 8 ? nowdir + 1 - 8 : nowdir + 1;
if (a[aux.x][aux.y] == 0 && dist[nowdir][aux.x][aux.y] + cost < dist[nextdir][aux.x][aux.y])
{
dist[nextdir][aux.x][aux.y] = dist[nowdir][aux.x][aux.y] + cost;
Q[1-p].push(stare(aux.x, aux.y, nextdir));
}
/// raman aici dar schimb directia la 45 de grade in partea cealalta cu cost 1
cost = 1, nextdir = nowdir - 1 < 0 ? nowdir - 1 + 8 : nowdir - 1;
if (a[aux.x][aux.y] == 0 && dist[nowdir][aux.x][aux.y] + cost < dist[nextdir][aux.x][aux.y])
{
dist[nextdir][aux.x][aux.y] = dist[nowdir][aux.x][aux.y] + cost;
Q[1-p].push(stare(aux.x, aux.y, nextdir));
}
}
p = 1 - p;
}
}
int main()
{
Read();
Solve();
if (!foundSol)
{
ofstream g("car.out");
g<<"-1\n";
g.close();
}
return 0;
}