Pagini recente » Cod sursa (job #2916405) | Cod sursa (job #2785529) | Cod sursa (job #852143) | Cod sursa (job #205136) | Cod sursa (job #217834)
Cod sursa(job #217834)
#include <fstream>
#include <iostream>
#define maxx 320000;
#include <vector>
#include <queue>
using namespace std;
struct cost_dir
{
vector<int> dir;
vector<int> ct;
};
cost_dir c[503][503];
int n,m,pi,pj,fi,fj;
int a[503][503],viz[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[pi][pj].ct.push_back(0);
c[pi][pj].dir.push_back(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 pushc(int vfi,int vfj,int i,int c)
{
c[vfi][vfj].dir.push_back(i);
c[vfi][vfj].ct.push_back(c);
}
*/
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)
{
//pushc(vfi+vi[i],vfj+vj[i],i,0);
c[vfi+vi[i]][vfj+vj[i]].dir.push_back(i);
c[vfi+vi[i]][vfj+vj[i]].ct.push_back(0);
}
else
{
int l=c[vfi][vfj].dir.size();
for(int v=0;v<l;v++)
{
int cc=diferenta(i,c[vfi][vfj].dir[v]);
//pushc(vfi+vi[i],vfj+vj[i],i,cc+c[vfi][vfj].ct[v]);
c[vfi+vi[i]][vfj+vj[i]].dir.push_back(i);
c[vfi+vi[i]][vfj+vj[i]].ct.push_back(cc+c[vfi][vfj].ct[v]);
}
}
}
}
}
int mini(int x,int y)
{
int mi=maxx;
for(int i=0;i<c[x][y].ct.size();i++)
if(mi>c[x][y].ct[i]&&mi!=0)
mi=c[x][y].ct[i];
return mi;
}
void fishi2()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<mini(i,j)<<" ";
cout<<endl;
}
}
int main()
{
citire();
autostrada();
fishi2();
ofstream g("car.out");
g<<mini(fi,fj)<<endl;
g.close();
return 0;
}