Pagini recente » Cod sursa (job #1333749) | Cod sursa (job #2109929) | Cod sursa (job #1280929) | Cod sursa (job #1563732) | Cod sursa (job #2327503)
#include <bits/stdc++.h>>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int n,m,i,j,dirx[10],diry[10],a[510][510],dyn[510][510][10];
pair<int,int> in,out;
struct Coada{
int x,y,dir;
};
queue<Coada> Q,q;
int main()
{
f>>n>>m;
f>>in.first>>in.second>>out.first>>out.second;
dirx[0]=-1;diry[0]= 0;
dirx[1]=-1;diry[1]= 1;
dirx[2]= 0;diry[2]= 1;
dirx[3]= 1;diry[3]= 1;
dirx[4]= 1;diry[4]= 0;
dirx[5]= 1;diry[5]=-1;
dirx[6]= 0;diry[6]=-1;
dirx[7]=-1;diry[7]=-1;
memset(dyn,127,sizeof(dyn));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>a[i][j];
for(i=0;i<=n+1;i++)a[i][0]=a[i][m+1]=1;
for(j=0;j<=m+1;j++)a[0][j]=a[n+1][j]=1;
for(i=0;i<8;i++)
{
Coada X;
X.x=in.first;
X.y=in.second;
X.dir=i;
Q.push(X);
dyn[in.first][in.second][i]=0;
}
while(!Q.empty())
{
while(!Q.empty())
{
Coada tp=Q.front();
Q.pop();
Coada nx=tp;
nx.x+=dirx[nx.dir];
nx.y+=diry[nx.dir];
if(!a[nx.x][nx.y])
if(dyn[nx.x][nx.y][nx.dir]>dyn[tp.x][tp.y][tp.dir])
{
dyn[nx.x][nx.y][nx.dir]=dyn[tp.x][tp.y][tp.dir];
Q.push(nx);
}
nx=tp;
nx.dir=(nx.dir+1)%8;
if(dyn[nx.x][nx.y][nx.dir]>dyn[tp.x][tp.y][tp.dir]+1)
{
dyn[nx.x][nx.y][nx.dir]=dyn[tp.x][tp.y][tp.dir]+1;
q.push(nx);
}
nx=tp;
nx.dir=(nx.dir+7)%8;
if(dyn[nx.x][nx.y][nx.dir]>dyn[tp.x][tp.y][tp.dir]+1)
{
dyn[nx.x][nx.y][nx.dir]=dyn[tp.x][tp.y][tp.dir]+1;
q.push(nx);
}
}
while(!q.empty())
{
Q.push(q.front());
q.pop();
}
}
int ans=1e9;
for(i=0;i<8;i++)
ans=min(ans,dyn[out.first][out.second][i]);
if(ans!=1e9)
g<<ans;
else
g<<-1;
}