Pagini recente » Cod sursa (job #2074682) | Cod sursa (job #1614101) | Cod sursa (job #1242973) | Cod sursa (job #512744) | Cod sursa (job #2094756)
#include <fstream>
#include <queue>
#include <bitset>
using namespace std;
ofstream fout ("car.out");
class InputReader {
public:
InputReader() {}
InputReader(const char *name) {
fin = fopen(name, "r");
buffpos = Size - 1;
}
inline InputReader &operator >>(int &n) {
char ch = nextpos();
while(ch < '0' || ch > '9') {
ch = nextpos();
}
n = 0;
while('0' <= ch && ch <= '9') {
n = n * 10 + ch - '0';
ch = nextpos();
}
return *this;
}
private:
FILE *fin;
static const int Size = 1 << 17;
int buffpos;
char buff[Size];
inline char nextpos() {
++ buffpos;
if(buffpos == Size) {
buffpos = 0;
fread(buff, Size, 1, fin);
}
return buff[ buffpos ];
}
} fin ("car.in");
const int nmax = 500;
const int inf = 1 << 30;
const int dl[ 8 ] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dc[ 8 ] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, ram;
int v[nmax + 2][nmax + 2];
int stx, sty, fnx, fny;
int d[nmax + 1][nmax + 1][ 8 ];
bitset< 8 > gata[nmax + 1][nmax + 1];
struct str {
int x, y, k;
str () {}
str (int _x, int _y, int _k) {
x = _x, y = _y, k = _k;
}
};
queue< str > q[ 5 ];
inline int cst (int x, int y) {
if (x > y) swap(x, y);
return min(y - x, 8 - y + x);
}
void extinde (str p, int ind) {
for (int dir = 0; dir < 8; ++ dir) {
int x = p.x + dl[ dir ], y = p.y + dc[ dir ];
if (gata[ x ][ y ][ dir ] == 1 || v[ x ][ y ] == 1)
continue;
int c = cst(p.k, dir);
if (d[ x ][ y ][ dir ] > d[ p.x ][ p.y ][ p.k ] + c) {
++ ram;
d[ x ][ y ][ dir ] = d[ p.x ][ p.y ][ p.k ] + c;
q[(ind + c) % 5].push(str(x, y, dir));
}
}
}
void bfs () {
ram = 0;
for (int i = 0; i < 8; ++ i) {
d[ stx ][ sty ][ i ] = 0;
++ ram;
q[ 0 ].push(str(stx, sty, i));
}
int ind = 0;
while (ram > 0) {
while (q[ ind ].empty()) {
ind = (ind + 1) % 5;
}
str p = q[ ind ].front(); q[ ind ].pop();
-- ram;
if (gata[ p.x ][ p.y ][ p.k ] == 1)
continue;
gata[ p.x ][ p.y ][ p.k ] = 1;
extinde(p, ind);
}
}
int main () {
fin >> n >> m >> stx >> sty >> fnx >> fny;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
fin >> v[ i ][ j ];
}
}
for (int i = 0; i <= n + 1; ++ i)
v[ i ][ 0 ] = v[ i ][m + 1] = 1;
for (int i = 0; i <= m + 1; ++ i)
v[ 0 ][ i ] = v[n + 1][ i ] = 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 ] = inf;
bfs();
int ans = inf;
for (int i = 0; i < 8; ++ i)
ans = min(ans, d[ fnx ][ fny ][ i ]);
if (ans == inf)
ans = -1;
fout << ans << "\n";
fout.close();
return 0;
}