Pagini recente » Cod sursa (job #425619) | Istoria paginii utilizator/burcurici | Cod sursa (job #1700714) | Cod sursa (job #3149277) | Cod sursa (job #1042024)
#include <fstream>
#include <queue>
#include <utility>
#include <cstring>
#include <cctype>
using namespace std;
const int MAX_N = 505;
const int dx[] = {1,1,0,-1,-1,-1, 0, 1};
const int dy[] = {0,1,1, 1, 0,-1,-1,-1};
int orig[3][3];
int bst[1 << 21];
int all[MAX_N][MAX_N];
bool bad[MAX_N][MAX_N];
struct state{
int info;
int x(){
return info % (1 << 9);
}
int y(){
return (info >> 9) % (1 << 9);
}
int dir(){
return (info >> 18);
}
state(int x, int y, int from):
info( (from << 18) + (y << 9) + x ){}
state():
info(0){}
};
queue<state> Qi[2];
ofstream out("car.out");
int n,m;
int x0,y0;
int x1,y1;
inline bool inside(state now){
return now.x() >= 1 && now.x() <= n && now.y() >= 1 && now.y() <= m && !bad[now.x()][now.y()];
}
inline void add(const state prev, const state now, queue<state> &Q, const int cst){
if(!inside(now))
return;
if(bst[prev.info] + cst < bst[now.info]){
bst[now.info] = bst[prev.info] + cst;
Q.push(now);
}
}
int chg[] = {0,1,-1};
int spread(){
memset(bst, 0x3f, sizeof(bst));
state now;
for(int i = 0 ; i < 8 ; ++i){
now = state( x0, y0, i );
bst[ now.info ] = 0;
Qi[0].push( now );
}
for(int dst = 0 ; !Qi[0].empty() || !Qi[1].empty() ; ++dst){
bool const cr = dst % 2;
queue<state> &Q = Qi[cr];
while(!Q.empty()) {
now = Q.front();
Q.pop();
const int x = now.x(),
y = now.y(),
dir = now.dir();
if(x == x1 && y == y1)
return dst;
for(int i = 0 ; i < 3 ; ++i){
int const ndir = (dir + chg[i] + 8) % 8;
add(now, state(x + dx[ndir] * (ndir == dir), y + dy[ndir] * (ndir == dir), ndir), Qi[(dst + (i > 0)) % 2], i > 0);
}
}
}
return -1;
}
struct parser{
parser():
DIM(1 << 14)
{
freopen("car.in", "r", stdin);}
const int DIM;
char buff[1 << 14];
char next_char(){
static int at = DIM - 1;
++at;
if(at == DIM){
fread(buff, 1, DIM, stdin);
at = 0;
}
return buff[at];
}
int next_int(){
char now;
do{
now = next_char();
}while(!isdigit(now));
int ret = 0;
do{
ret = ret * 10 + now - '0';
now = next_char();
}while(isdigit(now));
return ret;
}
template<class T>
void operator>> (T &val){
val = next_int();
}
}in;
int main(){
for(int i = 0 ; i < 8 ; ++i)
orig[dx[i]+1][dy[i]+1] = i;
in >> n;
in >> m;
in >> x0;
in >> y0;
in >> x1;
in >> y1;
for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j)
in >> bad[i][j];
out << spread() << "\n";
return 0;
}