Pagini recente » Cod sursa (job #209460) | Cod sursa (job #1356727) | Cod sursa (job #2085103) | Cod sursa (job #1043344) | Cod sursa (job #505848)
Cod sursa(job #505848)
# include <fstream>
# include <iostream>
# include <queue>
# include <algorithm>
# define infinit 2000000000
# define DIM 505
using namespace std;
int n, m, a[DIM][DIM], b[DIM][DIM], p[DIM][DIM][16], di[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dj[8]={0, 1, 1, 1, 0, -1, -1, -1};
int ist, jst, ifin, jfin, o[10][10], op[8]={4,5,6,7,0,1,2,3};
void read ()
{
ifstream fin ("car.in");
fin>>n>>m>>ist>>jst>>ifin>>jfin;
for(int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
fin>>a[i][j];
}
void init ()
{
for(int i=0;i<8;++i)
for(int j=i;j<8;++j)
if (j-i==4)o[i][j]=o[j][i]=0;
else if ((j-i)%4==2)o[i][j]=o[j][i]=2;
else if (j-i==5 || j-i==3)o[i][j]=o[j][i]=1;
else if (i+1==j || (i==0 && j==7))o[i][j]=o[j][i]=3;
else o[i][j]=o[j][i]=4;
}
int inline in_m (int i, int j)
{
if (i && j && i<=n && j<=m)return 1;
return 0;
}
void solve ()
{
queue<int>Qi, Qj;
Qi.push(ist);
Qj.push(jst);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if (!a[i][j])
for(int k=0;k<8;++k)
p[i][j][k]=infinit;
p[ist][jst][1]=-1;
// b[ist][jst]=0;
int i, j, ii, jj, ad;
while (Qi.size())
{
i=Qi.front();Qi.pop();
j=Qj.front();Qj.pop();
for(int k=0;k<8;++k)
{
ii=i+di[k];
jj=j+dj[k];
if (in_m (ii, jj) && !a[ii][jj])
{
ad=0;
if (p[i][j][1]==-1)
p[ii][jj][k]=0, ad=1;
else
for(int q=0;q<8;++q)
if (p[i][j][q]<infinit && p[i][j][q]+o[op[q]][k]<p[ii][jj][k])
p[ii][jj][k]=p[i][j][q]+o[op[q]][k], ad=1;
if (ad && (ii!=ifin || jj!=jfin))
{
Qi.push(ii);
Qj.push(jj);
}
}
}
}
}
int main ()
{
read ();
init();
solve ();
ofstream fout ("car.out");
int bst=infinit;
for(int k=0;k<8;++k)
if (p[ifin][jfin][k]<bst)
bst=p[ifin][jfin][k];
fout<<bst;
return 0;
}