Pagini recente » Cod sursa (job #1562062) | Cod sursa (job #2398530) | Cod sursa (job #1262315) | Cod sursa (job #699962) | Cod sursa (job #288395)
Cod sursa(job #288395)
#include <fstream>
#include <queue>
#include <bitset>
using namespace std;
int N,M,xi,yi,xf,yf;
bitset<512> a[512];
queue<int> L[2];
const int Inf=2000000000;
const int dx[8]={0,-1,-1,-1, 0,+1,1,1};
const int dy[8]={1,+1, 0,-1,-1,-1,0,1};
int d[8][512][512];
int main(){
int i,j,k;
ifstream f("car.in");
ofstream g("car.out");
f>>N>>M;
f>>xi>>yi>>xf>>yf;
for (i=1;i<=N;++i)
for (j=1;j<=M;++j)
f>>k,a[i][j]=k;
memset(d,0x3f,sizeof(d));
k=0;
for (i=0;i<8;++i){
L[k].push(xi + (yi<<9) + (i<<18));
d[i][xi][yi]=0;
}
int dir,x,y,_x,_y,_dir,now=0;
for (;L[0].size()+L[1].size()>0;++k){
now=k&1;
for (;!L[now].empty();L[now].pop()){
i=L[now].front();
dir=i>>18;
x=i&511;
y=(i>>9)&511;
if (x==xf && y==yf ) {g<<k;
return 0;}
_x=x+dx[dir];
_y=y+dy[dir];
if (_x>0 && _x<=N && _y>0 && _y<=M && !a[_x][_y])
if (d[dir][_x][_y]>k){
d[dir][_x][_y]=k;
L[now].push(_x + (_y<<9) + (dir<<18));
}
_dir=(dir+1)%8;
if (d[_dir][x][y]>k+1){
d[_dir][x][y]=k+1;
L[(now+1)&1].push(x+ (y<<9) + (_dir<<18));
}
_dir=(dir+7)%8;
if (d[_dir][x][y]>k+1){
d[_dir][x][y]=k+1;
L[(now+1)&1].push(x+ (y<<9) + (_dir<<18));
}
}
}
g<<-1;
return 0;
}