Pagini recente » Cod sursa (job #2024767) | Cod sursa (job #1333694) | Cod sursa (job #310313) | Cod sursa (job #7530) | Cod sursa (job #217930)
Cod sursa(job #217930)
//#include <cstdio>
#include <cstring>
#include <fstream>
using namespace std;
int n,m,a[510][510];
int dx[]={-1,-1, 0, 1, 1, 1, 0,-1};
int dy[]={ 0, 1, 1, 1, 0,-1,-1,-1};
int c[2000010],urm[2000010];
char viz[8][510][510];
ifstream fin("car.in");
ofstream fout("car.out");
int main()
{
int i, j, pc, qc, pu, qu, x, y, xb, yb, xf, yf, dir;
fin>>n>>m;
fin>>xb>>yb>>xf>>yf;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
fin>>a[i][j];
for (i = 0; i <= n+1; i++)
{
a[i][0]=1;
a[i][m+1]=1;
}
for (j=0; j<=m+1; j++)
{
a[0][j]=1;
a[n+1][j]=1;
}
for (i=0; i<8; i++)
{
c[i]=xb+(yb<<9)+(i<<18);
viz[i][xb][yb]=1;
}
pc=0;
qc=7;
pu=0;
qu=-1;
int cost=0;
int e=0;
while(1)
{
while (pc<=qc)
{
x=c[pc]&511;
y=(c[pc]>>9)&511;
if (x==xf && y==yf)
{
e=1;
break;
}
dir=c[pc]>>18;
if (!viz[dir][x+dx[dir]][y+dy[dir]] && !a[x+dx[dir]][y+dy[dir]])
{
c[++qc]=x+dx[dir]+((y+dy[dir])<<9)+(dir<<18);
viz[dir][x+dx[dir]][y+dy[dir]]=1;
}
pc++;
}
for (i=0; i<=qc; i++)
{
x=c[i]&511;
y=(c[i]>>9)&511;
dir=c[i]>>18;
if (!viz[(dir+1)&7][x][y])
{
urm[++qu]=x+(y<<9)+(((dir+1)&7)<<18);
viz[(dir+1)&7][x][y]=1;
}
dir--;
if (dir < 0)
dir=7;
if (!viz[dir][x][y])
{
urm[++qu]=x+(y<<9)+(dir<<18);
viz[dir][x][y]=1;
}
}
if (e)
break;
if (qu==-1)
{
cost=-1;
break;
}
cost++;
memcpy(c, urm, sizeof(c));
pc=0;
qc=qu;
qu=-1;
}
fout<<cost;
return 0;
}