Pagini recente » Cod sursa (job #1697510) | Cod sursa (job #2999102)
//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[4];
std::bitset<NMAX> mat[NMAX];
char explored[NMAX][NMAX];
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<4;++cost)
{
while(!q[cost&3].empty())
{
lastCost=cost;
p=q[cost&3].front();
q[cost&3].pop();
explored[p.i][p.j]|=1<<p.dir;
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] & (1<<next.dir)))
{
q[(cost-k)&3].push(next);
}
}
for(k=0;k<3;++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] & (1<<next.dir)))
{
q[(cost+k)&3].push(next);
}
}
}
}
}
if(!sol)
fprintf(g, "-1");
fclose(f);
fclose(g);
return 0;
}