Pagini recente » Cod sursa (job #3216787) | Cod sursa (job #1105494) | Cod sursa (job #972106) | Cod sursa (job #2604473) | Cod sursa (job #2121173)
#include <cstdio>
#include <queue>
#define MAX 505
using namespace std;
int n,m;
int xstart,ystart,xfinal,yfinal;
int drum[MAX][MAX],cost[MAX][MAX];
int xdir[8]= {-1,-1,0,1,1,1,0,-1};
int ydir[8]= {0,1,1,1,0,-1,-1,-1};
int costdir[8];
struct nod
{
int x,y,directie;
nod()
{
x = 0;
y = 0;
directie = -1;
}
};
void bordare()
{
for(int i = 0 ; i <= n + 1; i++)
{
drum[i][0] = 1;
drum[i][m+1] = 1;
}
for(int i = 0 ; i <= m+1 ; i++)
{
drum[0][i] = 1;
drum[n+1][i] = 1;
}
}
void updatecost(int directie)
{
if(directie == -1)
return;
costdir[directie]=0;
int stanga = directie,dreapta=directie;
int contor= 1;
while(contor <= 4)
{
if(stanga - contor < 0 )
stanga = 7 + stanga - contor + 1;
else
stanga -=contor;
if(dreapta + contor > 7)
dreapta = 0 + dreapta - contor - 1;
else
dreapta +=contor;
costdir[stanga] = contor;
costdir[dreapta]= contor;
contor++;
stanga = directie;
dreapta = directie;
}
}
void lee()
{
nod element,vecin;
queue<nod> coada;
element.x = xstart;
element.y = ystart;
element.directie = -1;
coada.push(element);
while(!coada.empty())
{
element = coada.front();
coada.pop();
updatecost(element.directie);
for(int k = 0 ; k < 8 ; k++)
{
vecin.x = element.x + xdir[k];
vecin.y = element.y + ydir[k];
vecin.directie = k;
if(drum[vecin.x][vecin.y] == 0)
{
if(cost[vecin.x][vecin.y] == 0)
{
cost[vecin.x][vecin.y] = cost[element.x][element.y]+costdir[k];
coada.push(vecin);
}
else
{
if(cost[vecin.x][vecin.y] > cost[element.x][element.y] + costdir[k])
{
cost[vecin.x][vecin.y] = cost[element.x][element.y]+costdir[k];
coada.push(vecin);
}
}
}
}
}
}
void read()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
scanf("%d %d\n%d %d %d %d",&n,&m,&xstart,&ystart,&xfinal,&yfinal);
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
scanf("%d ",&drum[i][j]);
}
drum[xstart][ystart] = 1;
bordare();
}
int main()
{
read();
int ok = 0;
for(int k = 0 ; k < 7 && ok == 0; k++)
if(drum[xfinal+xdir[k]][yfinal+ydir[k]] == 0)
ok = 1;
if(ok == 0)
printf("-1");
else
{
lee();
printf("%d",cost[xfinal][yfinal]);
}
return 0;
}