Pagini recente » Cod sursa (job #2130022) | Cod sursa (job #1810363) | Cod sursa (job #2156240) | Cod sursa (job #1561095) | Cod sursa (job #440568)
Cod sursa(job #440568)
#include <queue>
using namespace std;
const int NMAX = 501;
const int MMAX = 501;
const int INF = 1000000000;
const int lin[] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
const int col[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
int N, M;
pair<int, int> S;
pair<int, int> D;
bool C[NMAX][MMAX];
int A[NMAX][MMAX][9];
queue<int> Q;
void citire()
{
scanf("%d%d", &N, &M);
scanf("%d%d%d%d", &S.first, &S.second, &D.first, &D.second);
for(int i = 1 ; i <= N ; i++)
for(int j = 1 ; j <= M ; j++)
scanf("%d", &C[i][j]);
}
void init()
{
for(int i = 1 ; i <= N ; i++)
for(int j = 1 ; j <= M ; j++)
for(int k = 1 ; k <= 8 ; k++)
A[i][j][k] = INF;
for(int k = 1 ; k <= 8 ; k++)
A[S.first][S.second][k] = 0;
}
inline int dec(int x, int y)
{
if(x > y)
swap(x, y);
if(y - x <= 2)
return (y - x);
if(x + 8 - y <= 2)
return (x + 8 - y);
return 0;
}
inline int incad(int x, int y)
{
return(x && x <= N && y && y <= M);
}
void BFS()
{
int x, i, j, dir;
for(int k = 1 ; k <= 8 ; k++)
Q.push((S.first<<9) + S.second + (k<<18));
while(!Q.empty())
{
x = Q.front();
i = (x>>9) & 511;
j = x & 511;
dir = (x>>18);
for(int k = 1 ; k <= 8 ; k++)
if(dec(k, dir) <= 2 && !C[i + lin[k]][j + col[k]] && incad(i + lin[k], j + col[k]))
if(A[i][j][dir] + dec(k, dir) < A[i + lin[k]][j + col[k]][k])
{
A[i + lin[k]][j + col[k]][k] = A[i][j][dir] + dec(k, dir);
Q.push(((i+lin[k])<<9) + (j+col[k]) + (k<<18));
}
Q.pop();
}
}
void scrie()
{
int minim = INF;
for(int k = 1 ; k <= 8 ; k++)
minim = min(minim, A[D.first][D.second][k]);
printf("%d\n",minim);
}
int main()
{
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
citire();
init();
BFS();
scrie();
return 0;
}