Pagini recente » Cod sursa (job #558047) | Cod sursa (job #1572195) | Cod sursa (job #2735482) | Cod sursa (job #1816780) | Cod sursa (job #844158)
Cod sursa(job #844158)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
unsigned n, m, Si, Sj, Fi, Fj;
int Di[]={ -1, -1, -1, 0, 0, 1, 1, 1 };
int Dj[]={ -1, 0, 1, -1, 1, -1, 0, 1 };
int harta[505][505], mini=-1;
int detCost(int L, int C, int l, int c)
{
if(l==0 && c==0 || L==l && C==c) return 0;
else if( -L==l && -C==c) return 4;
switch(L)
{
case 1: { L=3; break; }
case 0: { L=2; break; }
case -1: { L=1; break; }
}
switch(C)
{
case 1: { C=3; break; }
case 0: { C=2; break; }
case -1: { C=1; break; }
}
switch(l)
{
case 1: { l=3; break; }
case 0: { l=2; break; }
case -1: { l=1; break; }
}
switch(c)
{
case 1: { c=3; break; }
case 0: { c=2; break; }
case -1: { c=1; break; }
}
l = L - l;
c = C - c;
if(l<0) l=-l;
if(c<0) c=-c;
if(l==0) if(c==1) return 1;
else if(c==2) return 2;
else;
else if(l==1) if(c==0) return 1;
else if(c==1) return 2;
else if(c==2) return 3;
else;
else if(c==0) return 2;
else return 3;
return 2;
}
void cautare(int ci, int cj, int dl, int dc, int cost)
{
int dir, l, c, tmp;
if(ci==Fi && cj==Fj) if(mini==-1) mini=cost;
else if(mini > cost) mini=cost;
else;
else if( (mini!=-1 && cost<mini) || mini==-1 )
for(dir=0; dir<8; ++dir)
{
l=ci+Di[dir];
c=cj+Dj[dir];
if(harta[l][c]==0)
{
harta[l][c]=1;
tmp=detCost(l-ci, c-cj, dl, dc);
cautare(l, c, l-ci, c-cj, cost+tmp);
harta[l][c]=0;
}
}
}
int main(void)
{
int i, j;
fin>>n>>m>>Si>>Sj>>Fi>>Fj;
for(i=1; i<=n; i++)
{
harta[i][0]=harta[i][m+1]=1;
for(j=1; j<=m; j++)
fin>>harta[i][j];
}
harta[1][1]=1;
harta[0][0] = harta[n+1][0] = harta[0][m+1] = harta[n+1][m+1] = 1;
for(j=1; j<=m; j++)
harta[0][j]=harta[n+1][j]=1;
cautare(Si, Sj, 0, 0, 0);
fout<<mini;
fin.close();
fout.close();
return 0;
}