Pagini recente » Cod sursa (job #1373708) | Cod sursa (job #2769728) | Cod sursa (job #2110666) | Cod sursa (job #2749856) | Cod sursa (job #1064912)
#include <fstream>
#include <set>
#define MAXN 505
#define INF 2000000000
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
struct nod{
int x,y,dir;};
int n,m,sx,sy,fx,fy,dp[MAXN][MAXN][8],dirx[8]={0,1,1,1,0,-1,-1,-1} ,diry[8]={-1,-1,0,1,1,1,0,-1},t1,t2,sol;
char s[MAXN];
bool a[MAXN][MAXN];
nod aux,aux2;
struct Comp{
bool operator()(nod p,nod q){
if(dp[p.x][p.y][p.dir]==dp[q.x][q.y][q.dir]){
if(p.x==q.x){
if(p.y==q.y)
return p.dir<q.dir;
return p.y<q.y;}
return p.x<q.x;}
return dp[p.x][p.y][p.dir]<dp[q.x][q.y][q.dir];}};
set<nod,Comp> v;
set<nod,Comp>::iterator it;
void citire();
int costcurba(int d1,int d2);
int main()
{
int i,j,k;
citire();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=0;k<8;k++)
dp[i][j][k]=INF;
aux.x=sx;aux.y=sy;
for(i=0;i<8;i++){
dp[sx][sy][i]=0;
aux.dir=i;
v.insert(aux);}
while(!v.empty()){
aux=(*v.begin());
v.erase(v.begin());
if(aux.x==fx&&aux.y==fy)
break;
for(i=0;i<8;i++){
if(a[aux.x+dirx[i]][aux.y+diry[i]])
continue;
t1=dp[aux.x+dirx[i]][aux.y+diry[i]][i];
t2=dp[aux.x][aux.y][aux.dir]+costcurba(aux.dir,i);
if(t1>t2){
aux2.x=aux.x+dirx[i];
aux2.y=aux.y+diry[i];
aux2.dir=i;
if(t1<INF)
v.erase(aux2);
dp[aux2.x][aux2.y][aux2.dir]=t2;
v.insert(aux2);}}}
sol=INF;
for(i=0;i<8;i++)
if(dp[fx][fy][i]<sol)
sol=dp[fx][fy][i];
if(sol==INF){
g<<"-1\n";
return 0;}
g<<sol<<'\n';
f.close();
g.close();
return 0;
}
void citire(){
int i,j;
f>>n>>m>>sx>>sy>>fx>>fy;
f.getline(s,MAXN,'\n');
for(i=1;i<=n;i++){
f.getline(s+2,MAXN,'\n');
for(j=1;j<=m;j++)
a[i][j]=s[2*j]-'0';
a[i][0]=a[i][m+1]=1;}
for(i=0;i<=m+1;i++)
a[0][i]=a[n+1][i]=1;}
int costcurba(int d1,int d2){
int cst;
cst=d1-d2;
if(cst<0)
cst=d2-d1;
if(cst>4)
cst=8-cst;
return cst;}