Pagini recente » Cod sursa (job #956383) | Cod sursa (job #215773) | Cod sursa (job #826562) | Cod sursa (job #209665) | Cod sursa (job #1096088)
#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[NMax][MMax][8];
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)
{
dist[xs][ys][i] = 0;
Q[0].push(stare(xs, ys, i));
}
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[xf][yf][aux.dir]<<"\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[aux.x][aux.y][nowdir] + cost < dist[aux.x + dx[nextdir]][aux.y + dy[nextdir]][nextdir])
{
dist[aux.x + dx[nextdir]][aux.y + dy[nextdir]][nextdir] = dist[aux.x][aux.y][nowdir] + 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 (dist[aux.x][aux.y][nowdir] + cost < dist[aux.x][aux.y][nextdir])
{
dist[aux.x][aux.y][nextdir] = dist[aux.x][aux.y][nowdir] + 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 (dist[aux.x][aux.y][nowdir] + cost < dist[aux.x][aux.y][nextdir])
{
dist[aux.x][aux.y][nextdir] = dist[aux.x][aux.y][nowdir] + 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;
}