Pagini recente » Cod sursa (job #1914773) | Cod sursa (job #699555) | Cod sursa (job #110753) | Cod sursa (job #2517452) | Cod sursa (job #1791988)
#include <fstream>
#include <queue>
#include <climits>
#define nmax 505
using namespace std;
unsigned int n,m;
bool P[nmax][nmax],viz[nmax][nmax];
unsigned int D[nmax][nmax];
struct el {unsigned int x,y;};
el dep[8];
unsigned int r8(int x)
{
x%=8;
if (x<0) x+=8;
return x;
}
struct pc{unsigned int cost,dir,x,y;};
queue <pc> q;
bool valid (pc t)
{
return ( (!P[t.x][t.y]) && 1<=t.x && t.x<=n && 1<=t.y && t.y<=m );
}
void bfs(el s, el f)
{
D[s.x][s.y]=0;
pc t,p;unsigned int i;
t.cost=0;
for (i=0;i<=7;i++)
{
t.x=s.x+dep[i].x;
t.y=s.y+dep[i].y;
if ( valid(t) )
{
t.dir=i;
D[t.x][t.y]=0;
q.push(t);
}
}
while (!q.empty())
{
p=q.front();q.pop();
//pastrarea directiei - 0
t=p;
t.x+=dep[t.dir].x;
t.y+=dep[t.dir].y;
if ( valid(t))
{
if (D[t.x][t.y]>t.cost)
{
D[t.x][t.y]=t.cost;
q.push(t);
}
}
//schimbarea directiei - 1,2,3
for (i=1;i<=3;i++)
{
t.dir=r8(p.dir+i);
t.cost=p.cost+i;
t.x=p.x+dep[t.dir].x;
t.y=p.y+dep[t.dir].y;
if ( valid(t) )
{
if (D[t.x][t.y]>t.cost)
{
D[t.x][t.y]=t.cost;
q.push(t);
}
}
t.dir=r8(p.dir-i);
t.cost=p.cost+i;
t.x=p.x+dep[t.dir].x;
t.y=p.y+dep[t.dir].y;
if ( valid(t) )
{
if (D[t.x][t.y]>t.cost)
{
D[t.x][t.y]=t.cost;
q.push(t);
}
}
}
//schimbarea sensului - 4
t=p;
t.dir=r8(t.dir+4);
t.cost+=4;
t.x+=dep[t.dir].x;
t.y+=dep[t.dir].y;
if ( valid(t))
{
if (D[t.x][t.y]>t.cost)
{
D[t.x][t.y]=t.cost;
q.push(t);
}
}
}
}
int main()
{
ifstream f("car.in");
ofstream g("car.out");
unsigned int i,j;
el s,fin;
f>>n>>m>>s.x>>s.y>>fin.x>>fin.y;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
f>>P[i][j],D[i][j]=INT_MAX;
{
dep[0].x=-1;dep[0].y=0;
dep[1].x=-1;dep[1].y=1;
dep[2].x=0;dep[2].y=1;
dep[3].x=1;dep[3].y=1;
dep[4].x=1;dep[4].y=0;
dep[5].x=1;dep[5].y=-1;
dep[6].x=0;dep[6].y=-1;
dep[7].x=-1;dep[7].y=-1;
}
bfs(s,fin);
if (D[fin.x][fin.y]==INT_MAX) g<<"-1\n";
else g<<D[fin.x][fin.y]<<'\n';
f.close();
g.close();
return 0;
}