Pagini recente » Cod sursa (job #2279834) | Cod sursa (job #494298) | Cod sursa (job #2885380) | Cod sursa (job #2181297) | Cod sursa (job #2920755)
#include <bits/stdc++.h>
#define L 505
#define DIR 8
#define BORDER -2
#define FREE 1000001
#define IMPOSSIBLE -1
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser 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;
}
res = FREE;
if (m[0][x][y] == BORDER || m[0][xx][yy] == BORDER)
res = IMPOSSIBLE;
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;
}
}
for (i = 0; i < DIR; i++)
res = min(res, m[i][xx][yy]);
if (res == FREE)
res = IMPOSSIBLE;
fout << res << "\n";
return 0;
}