Pagini recente » Cod sursa (job #239079) | Cod sursa (job #1735057)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f
#define NMAX 505
#define MOD 666013
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int v[NMAX][NMAX], viz[NMAX][NMAX][8];
int dlin[8]={0,-1,-1,-1,0,1,1,1};
int dcol[8]={1,1,0,-1,-1,-1,0,1};
queue<int> Q[2];
inline int code(int x, int y, int dir) {return (x<<12)+(y<<3)+dir;}
int main() {
int i,j,n,m,x0,x1,y1,y0,distact,ind,fr,x,y,dir;
fin>>n>>m>>x0>>y0>>x1>>y1;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j) fin>>v[i][j];
for(i=0;i<=n+1;++i) v[i][0]=v[i][m+1]=1;
for(i=0;i<=m+1;++i) v[0][i]=v[n+1][i]=1;
for(i=0;i<8;++i) Q[0].push(code(x0,y0,i));
distact=0;
while(!Q[0].empty() || !Q[1].empty()) {
ind=distact&1;
while(!Q[ind].empty()) {
fr=Q[ind].front();
Q[ind].pop();
x=fr>>12;
y=(fr>>3)&511;
dir=fr&7;
if(x==x1 && y==y1) {
fout<<distact;
return 0;
}
if(!v[x][y] && !viz[x][y][dir]) {
viz[x][y][dir]=1;
if(!v[x+dlin[dir]][y+dcol[dir]] && !viz[x+dlin[dir]][y+dcol[dir]][dir])
Q[ind].push(code(x+dlin[dir],y+dcol[dir],dir));
for(j=(dir+7)&7;j!=((dir+3)&7); j=(j+2)&7)
if(!viz[x][y][j]) Q[(ind+1)&1].push(code(x,y,j));
}
}
++distact;
}
fout<<-1;
return 0;
}