Pagini recente » Cod sursa (job #2219954) | Cod sursa (job #2068118) | Cod sursa (job #116688) | Cod sursa (job #1991579) | Cod sursa (job #217851)
Cod sursa(job #217851)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define maxx 320000;
using namespace std;
struct cost_dir
{
vector<int> dir;
vector<int> ct;
};
cost_dir c[200][200];
int n,m,pi,pj,fi,fj;
int a[502][502],viz[500][500];
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-1][pj-1].ct.push_back(0);
c[pi-1][pj-1].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-1][pj-1]=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]-1][vfj+vj[i]-1])
{
viz[vfi+vi[i]-1][vfj+vj[i]-1]=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]-1][vfj+vj[i]-1].dir.push_back(i);
c[vfi+vi[i]-1][vfj+vj[i]-1].ct.push_back(0);
}
else
{
int l=c[vfi-1][vfj-1].dir.size();
for(int v=0;v<l;v++)
{
int cc=diferenta(i,c[vfi-1][vfj-1].dir[v]);
c[vfi+vi[i]-1][vfj+vj[i]-1].dir.push_back(i);
c[vfi+vi[i]-1][vfj+vj[i]-1].ct.push_back(cc+c[vfi-1][vfj-1].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;
}
int main()
{
citire();
autostrada();
ofstream g("car.out");
g<<mini(fi-1,fj-1)<<endl;
g.close();
return 0;
}