Pagini recente » Cod sursa (job #3168283) | Cod sursa (job #2999125)
//Ilie Dumitru
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<queue>
const int NMAX=505;
const int MAXDIMQ=NMAX*NMAX*8;
struct pos
{
int i, j, dir;
};
int N, M;
std::queue<pos> q[3];
std::bitset<NMAX> mat[NMAX];
bool explored[NMAX][NMAX][8];
int main()
{
FILE *f=fopen("car.in", "r"), *g=fopen("car.out", "w");
int i, j, i0, i1, j0, j1, k, cost, x, lastCost=0;
bool sol=0;
pos p, next;
const int di[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int dj[8]={1, 1, 0, -1, -1, -1, 0, 1};
fscanf(f, "%d%d%d%d%d%d", &N, &M, &i0, &j0, &i1, &j1);
for(i=0;i<N;++i)
{
for(j=0;j<M;++j)
{
fscanf(f, "%d", &x);
mat[i][j]=x;
}
}
for(i=0;i<8;++i)
q[0].push({i0-1, j0-1, i});
for(cost=0;cost-lastCost<3;++cost)
{
while(!q[cost%3].empty())
{
lastCost=cost;
p=q[cost%3].front();
q[cost%3].pop();
if(!explored[p.i][p.j][p.dir])
{
explored[p.i][p.j][p.dir]=1;
if(p.i==i1-1 && p.j==j1-1)
{
fprintf(g, "%d\n", cost);
sol=1;
while(!q[0].empty())
q[0].pop();
while(!q[1].empty())
q[1].pop();
while(!q[2].empty())
q[2].pop();
}
else
{
for(k=-2;k<0;++k)
{
next.i=p.i+di[(p.dir+k+8)&7];
next.j=p.j+dj[(p.dir+k+8)&7];
next.dir=(p.dir+k+8)&7;
if(next.i>-1 && next.i<N && next.j>-1 && next.j<M && !mat[next.i][next.j] && !explored[next.i][next.j][next.dir])
q[(cost-k)%3].push(next);
}
for(k=0;k<3;++k)
{
next.i=p.i+di[(p.dir+k)&7];
next.j=p.j+dj[(p.dir+k)&7];
next.dir=(p.dir+k+8)&7;
if(next.i>-1 && next.i<N && next.j>-1 && next.j<M && !mat[next.i][next.j] && !explored[next.i][next.j][next.dir])
q[(cost+k)%3].push(next);
}
}
}
}
}
if(!sol)
fprintf(g, "-1");
fclose(f);
fclose(g);
return 0;
}