Pagini recente » Cod sursa (job #3228177) | Cod sursa (job #3179859) | Cod sursa (job #650597) | Cod sursa (job #2674903) | Cod sursa (job #505604)
Cod sursa(job #505604)
# 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);
p[ist][jst][0]=-1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
b[i][j]=infinit;
b[ist][jst]=0;
int i, j, ii, jj;
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];
int c=69;
if (p[i][j][0]==-1)
c=0;
else
for (int q=0;q<8;++q)
if (p[i][j][q] && c>o[op[q]][k])
c=o[op[q]][k];
if (in_m (ii, jj) && !a[ii][jj])
{
if (b[i][j]+c<b[ii][jj])
{
b[ii][jj]=b[i][j]+c;
p[ii][jj][k]=1;
if (ii!=ifin || jj!=jfin)
{
Qi.push(ii);
Qj.push(jj);
}
}
else
if (b[i][j]+c==b[ii][jj])
p[ii][jj][k]=1;
}
}
}
}
int main ()
{
read ();
init();
solve ();
ofstream fout ("car.out");
fout<<b[ifin][jfin];
return 0;
}