Pagini recente » Istoria paginii runda/pregatire_lot_juniori1/clasament | Profil StarGold2 | Cod sursa (job #1299943) | Cod sursa (job #720091) | Cod sursa (job #1256972)
//Roberto Deresu - FMI
//Re :)
#include<fstream>
#include<queue>
using namespace std;
int n,m,i,j,x,y,d,xi,yi,xf,yf,sol,a[505][505],b[10][505][505];
queue<int>q;
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];
}
void re()
{
q.push(xi);
q.push(yi);
q.push(0);
b[0][xi][yi] = 1;
sol = 0;
while(!q.empty())
{
x = q.front(), q.pop();
y = q.front(), q.pop();
d = q.front(), q.pop();
if(a[x+1][y] && (b[1][x+1][y] >= b[d][x][y] + val(d,1) || !b[1][x+1][y]))
{
b[1][x+1][y] = b[d][x][y] + val(d,1);
q.push(x+1);
q.push(y);
q.push(1);
}
if(a[x+1][y+1] && (b[2][x+1][y+1] >= b[d][x][y] + val(d,2) || !b[2][x+1][y+1]))
{
b[2][x+1][y+1] = b[d][x][y] + val(d,2);
q.push(x+1);
q.push(y+1);
q.push(2);
}
if(a[x][y+1] && (b[3][x][y+1] >= b[d][x][y] + val(d,3) || !b[3][x][y+1]))
{
b[3][x][y+1] = b[d][x][y] + val(d,3);
q.push(x);
q.push(y+1);
q.push(3);
}
if(a[x-1][y+1] && (b[4][x-1][y+1] >= b[d][x][y] + val(d,4) || !b[4][x-1][y+1]))
{
b[4][x-1][y+1] = b[d][x][y] + val(d,4);
q.push(x-1);
q.push(y+1);
q.push(4);
}
if(a[x-1][y] && (b[5][x-1][y] >= b[d][x][y] + val(d,5) || !b[5][x-1][y]))
{
b[5][x-1][y] = b[d][x][y] + val(d,5);
q.push(x-1);
q.push(y);
q.push(5);
}
if(a[x-1][y-1] && (b[6][x-1][y-1] >= b[d][x][y] + val(d,6) || !b[6][x-1][y-1]))
{
b[6][x-1][y-1] = b[d][x][y] + val(d,6);
q.push(x-1);
q.push(y-1);
q.push(6);
}
if(a[x][y-1] && (b[7][x][y-1] >= b[d][x][y] + val(d,7) || !b[7][x][y-1]))
{
b[7][x][y-1] = b[d][x][y] + val(d,7);
q.push(x);
q.push(y-1);
q.push(7);
}
if(a[x+1][y-1] && (b[8][x+1][y-1] >= b[d][x][y] + val(d,8) || !b[8][x+1][y-1]))
{
b[8][x+1][y-1] = b[d][x][y] + val(d,8);
q.push(x+1);
q.push(y-1);
q.push(8);
}
}
}
void afisare()
{
for(i=0;i<=8;i++)
if(b[i][xf][yf] && (b[i][xf][yf] < sol || !sol)) sol = b[i][xf][yf];
fout<<sol-1;
}
int main()
{
citire();
re();
afisare();
return 0;
}