Pagini recente » Cod sursa (job #745358) | Cod sursa (job #1395727) | Cod sursa (job #458967) | Cod sursa (job #612482) | Cod sursa (job #1987950)
#include <fstream>
#include <cmath>
#include <algorithm>
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;
}
};
int n, m, l1, c1, l2, c2, a[505][505], t[505][505][8], st[3], dr[3];
int q[3][1000005];
struct coada{
int l, c, d;
}z;
short dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
short dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
inline int cost(int d1, int d2){
int dif = abs(d2 - d1);
return min(8 - dif, dif);
}
inline void bfs(){
st[0] = st[1] = st[2] = 1; dr[0] = 0;
int k = 0;
for(short kr = 0; kr < 8 ; ++kr){
if(a[l1 + dx[kr]][c1 + dy[kr]] == 1 && l1 + dx[kr] >= 0 && l1 + dx[kr] <= n && c1 + dy[kr] >= 0 && c1 + dy[kr] <= m) continue ;
t[l1][c1][kr] = 0;
q[0][++dr[k]] = (l1 << 9) + c1 + (kr << 18);
}
while(st[0] <= dr[0] || st[1] <= dr[1] || st[2] <= dr[2]){
while(st[k] > dr[k]){
++k;
if(k > 2) k = k - 3;
}
int x = q[k][st[k]++];
z.d = x >> 18;
z.c = (x & 511); z.l = (x >> 9) & 511;
short cr = z.d, steps = 0, ok = 0, usu = 0;
while(steps <= 2){
short l = dx[cr] + z.l;
short c = dy[cr] + z.c;
if(l >= 1 && c >= 1 && l <= n && c <= m && a[l][c] == 0){
if(t[l][c][cr] > t[z.l][z.c][z.d] + usu){
t[l][c][cr] = t[z.l][z.c][z.d] + usu;
if(l == l2 && c == c2)
break ;
int newk = (k + usu);
if(newk > 2) newk -= 3;
q[newk][++dr[newk]] = (l << 9) + c + (cr << 18);
}
}
++steps; ++cr; ++usu;
if(cr == 8) cr = 0;
}
cr = z.d - 1; steps = 0; usu = 1;
if(ok == 1) steps = 2;
while(steps <= 1){
if(cr < 0) cr = 7;
short l = dx[cr] + z.l;
short c = dy[cr] + z.c;
if(l >= 1 && c >= 1 && l <= n && c <= m && a[l][c] == 0){
if(t[l][c][cr] > t[z.l][z.c][z.d] + usu){
t[l][c][cr] = t[z.l][z.c][z.d] + usu;
if(l == l2 && c == c2)
break ;
int newk = (k + usu);
if(newk > 2) newk -= 3;
q[newk][++dr[newk]] = (l << 9) + c + (cr << 18);
}
}
++steps; --cr; ++usu;
}
}
}
int main()
{
InParser fin("car.in");
ofstream fout("car.out");
fin >> n >> m;
fin >> l1 >> c1 >> l2 >> c2;
for(int i = 1; i <= n ; ++i)
for(int j = 1; j <= m ; ++j){
fin >> a[i][j];
for(short k = 0; k < 8 ; ++k)
t[i][j][k] = 2000000000;
}
bfs();
int Sol = 2000000000;
for(short k = 0; k < 8 ; ++k)
Sol = min(Sol, t[l2][c2][k]);
if(Sol == 2000000000) fout<<"-1";
else fout << Sol;
return 0;
}