Pagini recente » Cod sursa (job #2941644) | Cod sursa (job #2324141) | Cod sursa (job #2214890) | Cod sursa (job #372803) | Cod sursa (job #1060302)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define DIM 502
#define INF 99999
ifstream is ("car.in");
ofstream os ("car.out");
struct Cel{int i, j;} Start, Finish;
queue <Cel> Q;
const int di[] = {-1,-1,0,1,1,1,0,-1};
const int dj[] = {0,1,1,1,0,-1,-1,-1};
bool a[DIM][DIM];
int D[DIM][DIM];
int Cost[DIM][DIM];
int n, m;
void Read();
void BFS();
void Solve();
bool Ok(int i, int j);
int SetPrice(int i, int j, int x);
int MOD(int x, int y);
void DEBUG();
int main()
{
Read();
BFS();
Solve();
//DEBUG();
is.close();
os.close();
return 0;
}
void Solve()
{
if (D[Finish.i][Finish.j] == 0)
{
os << -1;
return;
}
os << Cost[Finish.i][Finish.j];
};
void Read()
{
is >> n >> m;
is >> Start.i >> Start.j >> Finish.i >> Finish.j;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
is >> a[i][j];
};
void BFS()
{
Cel Ac;
int i, j, iv, jv;
Q.push(Start);
D[Start.i][Start.j] = 1;
while (!Q.empty())
{
Ac = Q.front(), Q.pop();
i = Ac.i, j = Ac.j;
for (int dir = 0; dir < 8; dir++)
{
iv = i + di[dir];
jv = j + dj[dir];
if (Ok(iv, jv) && D[iv][jv] == 0 && a[iv][jv] == 0)
{
D[iv][jv] = D[i][j]+1;
Ac.i = iv, Ac.j = jv;
Q.push(Ac);
}
if (D[i][j] >= 3)
Cost[i][j] = SetPrice(i, j, D[i][j]);
}
}
};
int SetPrice(int i, int j, int x)
{
int iv, jv, in, jn;
int rev = INF, mod;
for (int dir1 = 0; dir1 < 8; ++dir1)
{
iv = i + di[dir1];
jv = j + dj[dir1];
if (D[iv][jv] == x-1 && Ok(iv, jv))
for (int dir2 = 0; dir2 < 8; ++dir2)
{
in = iv + di[dir2];
jn = jv + dj[dir2];
if (D[in][jn] == x-2 && Ok(in, jn))
{
mod = MOD(dir1, dir2);
mod += Cost[iv][jv];
rev = min(rev, mod);
}
}
}
return rev;
};
int MOD(int x, int y)
{
if (x == y-4 || x-4 == y)
return 0;
if (x == y-3 || x-3 == y || x-5 == y || x == y-5)
return 1;
if (x == y-2 || x-2 == y || x-6 == y || x == y-6)
return 2;
if (x == y-1 || x-1 == y || x-7 == y || x == y-7)
return 3;
return 0;
};
bool Ok(int i, int j)
{
if (i < 1 || j < 1 || i > n || j > m) return false;
return true;
};
void DEBUG()
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
os << Cost[i][j] << ' ';
os << '\n';
}
os << '\n';
};