Pagini recente » Cod sursa (job #2409998) | Cod sursa (job #1162154) | Cod sursa (job #192904) | Cod sursa (job #408698) | Cod sursa (job #2920749)
#include <bits/stdc++.h>
#define L 505
#define DIR 8
#define BORDER -2
#define FREE 1000001
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int m[DIR][L][L], vx[DIR][L * L], vy[DIR][L * L], i1[DIR], i2[DIR];
int dl[DIR] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[DIR] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(){
int l, c, x, y, xx, yy, i, j, k, ok1, ok2, cost, res;
fin >> l >> c >> x >> y >> xx >> yy;
for (i = 1; i <= l; i++)
for (j = 1; j <= c; j++){
fin >> m[0][i][j];
if (m[0][i][j] == 1)
m[0][i][j] = BORDER;
else
m[0][i][j] = FREE;
for (k = 1; k < DIR; k++)
m[k][i][j] = m[0][i][j];
}
for (k = 0; k < DIR; k++){
for (i = 0; i < l + 2; i++)
m[k][i][0] = m[k][i][c + 1] = BORDER;
for (j = 0; j < c + 2; j++)
m[k][0][j] = m[k][l + 1][j] = BORDER;
}
for (i = 0; i < DIR; i++){
m[i][x][y] = 0;
vx[i][i2[i]] = x;
vy[i][i2[i]] = y;
i2[i]++;
}
ok1 = ok2 = 1;
while (ok1 && ok2){
for (i = 0; i < DIR; i++){
if (i1[i] < i2[i]){
x = vx[i][i1[i]];
y = vy[i][i1[i]];
if (m[i][x + dl[i]][y + dc[i]] != BORDER && m[i][x + dl[i]][y + dc[i]] > m[i][x][y]){
m[i][x + dl[i]][y + dc[i]] = m[i][x][y];
vx[i][i2[i]] = x + dl[i];
vy[i][i2[i]] = y + dc[i];
i2[i]++;
}
for (j = 0; j < DIR; j++)
if (j != i && j != (i + DIR / 2) % DIR){
cost = min(abs(i - j), DIR - abs(i - j));
if (m[j][x][y] > m[i][x][y] + cost){
m[j][x][y] = m[i][x][y] + cost;
vx[j][i2[j]] = x;
vy[j][i2[j]] = y;
i2[j]++;
}
}
i1[i]++;
}
}
ok1 = ok2 = 0;
for (i = 0; i < DIR; i++){
if (i1[i] < i2[i])
ok1 = 1;
if (m[i][xx][yy] == FREE)
ok2 = 1;
}
}
res = FREE;
for (i = 0; i < DIR; i++)
res = min(res, m[i][xx][yy]);
fout << res << "\n";
return 0;
}