Pagini recente » Borderou de evaluare (job #2016802) | Cod sursa (job #921200) | Cod sursa (job #447877) | Borderou de evaluare (job #2456578) | Cod sursa (job #2889204)
#import<fstream>
#import<vector>
#import<algorithm>
#import<cmath>
#import<queue>
#import<unordered_set>
#import<string>
using namespace std;
ifstream cin("car.in");
ofstream cout("car.out");
int rez[501][501][10];
const int dir=8,inf=2e9;
int dc[]={ 1, 1, 1, 0,-1,-1,-1, 0};
int dl[]={-1, 0, 1, 1, 1, 0,-1,-1};
int n,m;
bool inside(const int x,const int y)
{
return (x>0 && x<=m && y>0 && y<=n);
}
bool ok[501][501];
struct idk
{
int s,x,y,dir;
};
struct sortt
{
bool operator()(idk a,idk b)
{
return a.s>=b.s;;
}
};
main()
{
int xi,xf,yi,yf;
cin>>n>>m>>yi>>xi>>yf>>xf;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ok[j][i];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=0;k<dir;k++)
{
rez[j][i][k]=inf;
}
}
}
priority_queue<idk,vector<idk>,sortt>q;
for(int k=0;k<dir;k++)
{
rez[xi][yi][k]=0;
q.push({0,xi,yi,k});
}
int maxx=2e9;
while(!q.empty())
{
idk last=q.top();
q.pop();
if(rez[last.x][last.y][last.dir]>maxx)
{
break;
}
if(rez[last.x][last.y][last.dir]!=last.s)
{
continue;
}
for(int i=-2;i<=2;i++)
{
int directie=last.dir+i;
if(directie<0)
{
directie+=8;
}
else if(directie>=8)
{
directie-=8;
}
int x=last.x+dc[directie];
int y=last.y+dl[directie];
if(!inside(x,y) || ok[x][y])
{
continue;
}
if(rez[x][y][directie]>last.s+abs(i))
{
rez[x][y][directie]=last.s+abs(i);
if(x==xf && yf==y)
{
maxx=0;
for(int j=0;j<8;j++)
{
maxx=max(rez[x][y][j],maxx);
}
}
else
{
q.push({last.s+abs(i),x,y,directie});
}
}
}
}
int minn=2e9;
for(int k=0;k<dir;k++)
{
minn=min(minn,rez[xf][yf][k]);
}
if(minn!=2e9)
{
cout<<minn;
}
else cout<<-1;
}