Pagini recente » Cod sursa (job #899246) | Cod sursa (job #2989504) | Cod sursa (job #937071) | Cod sursa (job #1828979) | Cod sursa (job #3172884)
#include <vector>
#include <queue>
#include <fstream>
#include <climits>
#include <algorithm>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
struct coord {
int i, j;
};
struct elemcoada {
int dir;
coord node;
};
const int LMAX = 505;
bool ai[LMAX][LMAX];
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
queue<elemcoada> Q[3];
vector<vector<vector<int>>>af;
void dial(int si, int sj) {
elemcoada aux;
aux.node.i = si;
aux.node.j = sj;
for (int i = 0; i < 8; i++) {
aux.dir = i;
af[i][si][sj] = 0;
Q[0].push(aux);
}
int nrelem, currq, dir, i, j, l, inou, jnou, cost;
nrelem = 8;
currq = 0;
while (nrelem) {
while (Q[currq].empty()) {
currq = (currq + 1) % 3;
}
aux = Q[currq].front();
Q[currq].pop();
nrelem--;
dir = aux.dir;
i = aux.node.i;
j = aux.node.j;
l = dir - 2; //la stanga
if (l < 0) {
l = l + 8;
}
for (int cnt = 0; cnt < 5; cnt++) {
inou = i + dy[l];
jnou = j + dx[l];
cost = abs(2 - cnt);
if (ai[inou][jnou] == 0 && af[l][inou][jnou] > af[dir][i][j] + cost) {
af[l][inou][jnou] = af[dir][i][j] + cost;
aux.dir = l;
aux.node.i = inou;
aux.node.j = jnou;
Q[cost].push(aux);
nrelem++;
}
l = (l + 1) % 8;
}
}
}
int main() {
int n, m, si, sj, fi, fj, i, j, l;
fin >> n >> m >> si >> sj >> fi >> fj;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
fin >> ai[i][j];
}
}
for (i = 0; i <= n+1; i++) {
ai[i][0] = ai[i][m+1] = 1;
}
for (j = 0; j <= m+1; j++) {
ai[0][j] = ai[n+1][j] = 1;
}
af.assign(8,vector<vector<int>>(n+1,vector<int>(m+1,INT_MAX)));
dial(si, sj);
int mini = INT_MAX;
for (l = 0; l < 8; l++) {
if (af[l][fi][fj] != INT_MAX) {
mini = min(mini, af[l][fi][fj]);
}
}
if (mini == INT_MAX) {
fout << -1;
}
else {
fout << mini;
}
fin.close();
fout.close();
return 0;
}