Pagini recente » Cod sursa (job #428715) | Cod sursa (job #1724320) | Cod sursa (job #145545) | Cod sursa (job #527879) | Cod sursa (job #1256298)
//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)
{
if(d1 == 0)return 0;
if(d1 < d2)d1 = d1^d2^(d2 = d1);
if(d1-d2 == 4)return 4;
if(d1-d2 == 3 || d1-d2 == 5)return 3;
if(d1-d2 == 2 || d1-d2 == 6)return 2;
if(d1-d2 == 1 || d1-d2 == 7)return 1;
if(d1-d2 == 0)return 0;
}
void citire()
{
fin>>n>>m;
fin>>xi>>yi>>xf>>yf;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fin>>a[i][j],a[i][j]=1-a[i][j];
}
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-1] > 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;
}