Pagini recente » Cod sursa (job #1087527) | Cod sursa (job #2782287) | Cod sursa (job #1035128) | Cod sursa (job #868531) | Cod sursa (job #1256291)
//Roberto Deresu - FMI
//Re :)
#include<fstream>
#include<queue>
using namespace std;
int n,m,i,j,x,y,d,xi,yi,xf,yf,a[505][505],b[505][505];
queue<int>q;
char s[1007];
ifstream fin("car.in");
ofstream fout("car.out");
int val(int d1,int d2)
{
int c = 0;
if(!d1 || d1 == d2)return 0;
if(d1 < d2)d1 = d1^d2^(d2 = d1);
if((d1-1)/4 != (d2-1)/4) d1 = 9-d1, c=1;
if(d1>d2) return d1-d2+c;
else return d2-d1+c;
}
void citire()
{
fin>>n>>m;
fin>>xi>>yi>>xf>>yf;
fin.getline(s,sizeof(s));
for(i=1;i<=n;i++)
{
fin.getline(s,sizeof(s));
for(j=0;j<m;j++)
a[i][j+1] = 1-(s[2*j]-'0');
}
}
int main()
{
citire();
q.push(xi);
q.push(yi);
q.push(0);
b[xi][yi]=1;
while(!q.empty())
{
x=q.front(), q.pop();
y=q.front(), q.pop();
d=q.front(), q.pop();
if(a[x+1][y] && (b[x+1][y] > b[x][y] + val(d,1) || !b[x+1][y]))
{
b[x+1][y] = b[x][y] + val(d,1);
q.push(x+1);
q.push(y);
q.push(1);
}
if(a[x+1][y+1] && (b[x+1][y+1] > b[x][y] + val(d,2) || !b[x+1][y+1]))
{
b[x+1][y+1] = b[x][y] + val(d,2);
q.push(x+1);
q.push(y+1);
q.push(2);
}
if(a[x][y+1] && (b[x][y+1] > b[x][y] + val(d,3) || !b[x][y+1]))
{
b[x][y+1] = b[x][y] + val(d,3);
q.push(x);
q.push(y+1);
q.push(3);
}
if(a[x-1][y+1] && (b[x-1][y+1] > b[x][y] + val(d,4) || !b[x-1][y+1]))
{
b[x-1][y+1] = b[x][y] + val(d,4);
q.push(x-1);
q.push(y+1);
q.push(4);
}
if(a[x-1][y] && (b[x-1][y] > b[x][y] + val(d,5) || !b[x-1][y]))
{
b[x-1][y] = b[x][y] + val(d,5);
q.push(x-1);
q.push(y);
q.push(5);
}
if(a[x-1][y-1] && (b[x-1][y] > b[x][y] + val(d,6) || !b[x-1][y-1]))
{
b[x-1][y-1] = b[x][y] + val(d,6);
q.push(x-1);
q.push(y-1);
q.push(6);
}
if(a[x][y-1] && (b[x][y-1] > b[x][y] + val(d,7) || !b[x][y-1]))
{
b[x][y-1] = b[x][y] + val(d,7);
q.push(x);
q.push(y-1);
q.push(7);
}
if(a[x+1][y-1] && (b[x+1][y-1] > b[x][y] + val(d,8) || !b[x+1][y-1]))
{
b[x+1][y-1] = b[x][y] + val(d,8);
q.push(x+1);
q.push(y-1);
q.push(8);
}
}
fout<<b[xf][yf]-1;
return 0;
}