Pagini recente » Cod sursa (job #623098) | Cod sursa (job #710510) | Cod sursa (job #927226) | Cod sursa (job #2609575) | Cod sursa (job #217777)
Cod sursa(job #217777)
#include <fstream>
#include <iostream>
#define maxx 320000;
#include <queue>
using namespace std;
int n,m,pi,pj,fi,fj;
int a[503][503],c[503][503],viz[503][503],dir[503][503];
int vi[8]={-1,-1,-1,0,1,1,1,0};
int vj[8]={-1,0,1,1,1,0,-1,-1};
queue<int> q;
void init()
{
for(int i=0;i<=n+1;i++)
{
a[i][0]=1;
a[i][m+1]=1;
}
for(int i=0;i<=m+1;i++)
{
a[0][i]=1;
a[n+1][i]=1;
}
c[fi][fj]=0;
}
void citire()
{
ifstream f("car.in");
f>>n>>m;
f>>pi>>pj>>fi>>fj;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f>>a[i][j];
c[i][j]=-1;
if(a[i][j]==0)
c[i][j]=maxx;
}
init();
}
int diferenta(int x,int y)
{
if(x>y)
{
int aux=x;
x=y;
y=aux;
}
int cost=0;
int z=1;
for(int i=0;i<y-x;i++)
{
cost+=z;
if(cost==4)
z*=-1;
if(cost==0)
z*=-1;
}
return cost;
}
void autostrada()
{
viz[pi][pj]=1;
q.push(pi);
q.push(pj);
while(!q.empty())
{
int vfi=q.front();
q.pop();
int vfj=q.front();
q.pop();
for(int i=0;i<8;i++)
if(a[vfi+vi[i]][vfj+vj[i]]==0)
{
if(!viz[vfi+vi[i]][vfj+vj[i]])
{
viz[vfi+vi[i]][vfj+vj[i]]=1;
q.push(vfi+vi[i]);
q.push(vfj+vj[i]);
}
if(vfi==pi&&vfj==pj)
{
c[vfi+vi[i]][vfj+vj[i]]=0;
dir[vfi+vi[i]][vfj+vj[i]]=i;
}
else
{
int cc=diferenta(i,dir[vfi][vfj]);
if(c[vfi+vi[i]][vfj+vj[i]]>c[vfi][vfj]+cc)
{
dir[vfi+vi[i]][vfj+vj[i]]=i;
c[vfi+vi[i]][vfj+vj[i]]=c[vfi][vfj]+cc;
}
}
}
}
}
void fishi()
{
cout<<" ";
for(int i=1;i<=m;i++)
cout<<i<<" ";
cout<<endl;
for(int i=1;i<=n;i++)
{
cout<<i<<" ";
for(int j=1;j<=m;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}
}
void autostrada2()
{
viz[fi][fj]=1;
q.push(fi);
q.push(fj);
while(!q.empty())
{
int vfi=q.front();
q.pop();
int vfj=q.front();
q.pop();
for(int i=0;i<8;i++)
if(a[vfi+vi[i]][vfj+vj[i]]==0)
{
if(!viz[vfi+vi[i]][vfj+vj[i]])
{
viz[vfi+vi[i]][vfj+vj[i]]=1;
q.push(vfi+vi[i]);
q.push(vfj+vj[i]);
}
if(vfi==fi&&vfj==fj)
{
c[vfi+vi[i]][vfj+vj[i]]=0;
dir[vfi+vi[i]][vfj+vj[i]]=i;
}
else
{
int cc=diferenta(i,dir[vfi][vfj]);
if(c[vfi+vi[i]][vfj+vj[i]]>=c[vfi][vfj]+cc)
{
dir[vfi+vi[i]][vfj+vj[i]]=i;
c[vfi+vi[i]][vfj+vj[i]]=c[vfi][vfj]+cc;
}
}
}
}
}
int main()
{
citire();
autostrada2();
fishi();
ofstream g("car.out");
g<<c[pi][pj]<<endl;
g.close();
return 0;
}