Pagini recente » Cod sursa (job #2768255) | Cod sursa (job #550058) | Cod sursa (job #3189155) | Cod sursa (job #1519379) | Cod sursa (job #3298767)
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("car.in");
ofstream fcout("car.out");
typedef long long ll;
const int N = 1e6 + 5;
const int M = 505;
bool v[M][M], viz[M][M][8];
int n, m, d[M][M][8];
int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
/**
7 0 1
6 2
5 4 3
*/
struct nod
{
short i, j;
char niv; /// = k
};
vector<nod> L[N];
int main()
{
int i1, j1, i2, j2;
fcin >> n >> m >> i1 >> j1 >> i2 >> j2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fcin >> v[i][j];
for (int i = 0; i <= n + 1; i++)
v[i][0] = v[i][m + 1] = 1;
for (int j = 0; j <= m + 1; j++)
v[0][j] = v[n + 1][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < 8; k++)
d[i][j][k] = 1e9;
for (int k = 0; k < 8; k++)
{
d[i1][j1][k] = 0;
L[0].push_back({i1, j1, k});
}
for (int i = 0; i < N; i++)
for (int j = 0; j < L[i].size(); j++)
{
nod e = L[i][j];
if (!viz[e.i][e.j][e.niv])
{
viz[e.i][e.j][e.niv] = 1;
// cout << e.i << ' ' << e.j << ' ' << (int) e.niv << endl;
for (int k = 0; k < 8; k++)
{
int ii, jj, c;
ii = e.i + di[k];
jj = e.j + dj[k];
c = d[e.i][e.j][e.niv] + min(abs(k - e.niv), 8 - abs(k - e.niv));
if (!v[ii][jj] && !viz[ii][jj][k] &&
c < d[ii][jj][k])
{
// cout << e.i << ' ' << e.j << ' ' << (int) e.niv << ' '<<
// ii << ' ' << jj << ' ' << k << ' ' << c << endl;
d[ii][jj][k] = c;
L[c].push_back({ii, jj, k});
}
}
}
}
int rasp = 1e9;
// for (int k = 0; k < 8; k++)
// cout << d[i2][j2][k] << ' ';
for (int k = 0; k < 8; k++)
rasp = min(rasp, d[i2][j2][k]);
fcout << rasp;
fcin.close();
fcout.close();
return 0;
}