Pagini recente » Cod sursa (job #214228) | Cod sursa (job #2702311) | Cod sursa (job #1976047) | Cod sursa (job #296694) | Cod sursa (job #217793)
Cod sursa(job #217793)
#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][9];
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;
//queue<int> dir[503][503];
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[pi][pj]=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 push(int vfi,int vfj,int i)
{
dir[vfi][vfj][0]++;
dir[vfi][vfj][dir[vfi][vfj][0]]=i;
}
void pushpush(int vfi,int vfj,int i)
{
dir[vfi][vfj][0]=1;
dir[vfi][vfj][1]=i;
}
int dif(int i,int vfi, int vfj)
{
int pp=10;
for(int j=1;j<=dir[vfi][vfj][0];j++)
{
int xxx=dir[vfi][vfj][j];
int po=diferenta(i,xxx);
if(pp>po)
pp=po;
//pop(vfi,vfj);
}
return pp;
}
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]].push(i);
pushpush(vfi+vi[i],vfj+vj[i],i);
}
else
{
int cc=dif(i,vfi,vfj);
if(c[vfi+vi[i]][vfj+vj[i]]>=c[vfi][vfj]+cc)
{
//dir[vfi+vi[i]][vfj+vj[i]].push(i);
if(c[vfi+vi[i]][vfj+vj[i]]==c[vfi][vfj]+cc)
push(vfi+vi[i],vfj+vj[i],i);
else pushpush(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;
}
}
int main()
{
citire();
autostrada();
fishi();
ofstream g("car.out");
g<<c[fi][fj]<<endl;
g.close();
return 0;
}