Pagini recente » Cod sursa (job #799950) | Cod sursa (job #798311) | Cod sursa (job #1634676) | Cod sursa (job #2460298) | Cod sursa (job #3235766)
//dial
#include <bits/stdc++.h>
std :: ifstream in ("car.in");
std :: ofstream out ("car.out");
const int NMAX = 5e2 + 5;
const int INF = 2e9;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, - 1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n;
int m;
int xs;
int ys;
int xf;
int yf;
int cnt;
int actual;
bool a[NMAX][NMAX];
bool visited[NMAX][NMAX][8];
int dist[NMAX][NMAX];
std :: queue <std :: pair<std :: pair<int, int>, int>> q[3];
inline bool inbound(int i, int j)
{
return i >= 1 && j >= 1 && i <= n && j <= n;
}
void dial()
{
while(cnt)
{
while(q[actual].empty())
{
actual ++;
actual %= 3;
}
int x = q[actual].front().first.first;
int y = q[actual].front().first.second;
int dir = q[actual].front().second;
q[actual].pop();
cnt --;
if(visited[x][y][dir] == 0)
{
visited[x][y][dir] = true;
//pastrez dir
for(int i = -2; i <= 2; i ++)
{
int ac_dir = dir + i;
if(ac_dir < 0)
{
ac_dir += 8;
}
ac_dir %= 8;
int l = x + dx[ac_dir];
int c = y + dy[ac_dir];
if(inbound(l, c) && a[l][c] == 0 && dist[x][y] + abs(i) < dist[l][c])
{
cnt ++;
q[(actual + abs(i)) % 3].push(std :: make_pair(std :: make_pair(l, c), ac_dir));
dist[l][c] = dist[x][y] + abs(i);
}
}
/*if(inbound(x + dx[dir], y + dy[dir]) && a[x + dx[dir]][y + dy[dir]] == 0 && dist[x][y] < dist[x + dx[dir]][y + dy[dir]])
{
q[actual].push(std :: make_pair(std :: make_pair(x + dx[dir], y + dy[dir]), dir));
dist[x + dx[dir]][y + dy[dir]] = dist[x][y];
cnt ++;
}
dir ++;
dir %= 8;
if(inbound(x + dx[dir], y + dy[dir]) && a[x + dx[dir]][y + dy[dir]] == 0 && dist[x][y] + 1 < dist[x + dx[dir]][y + dy[dir]])
{
q[(actual + 1) % 3].push(std :: make_pair(std :: make_pair(x + dx[dir], y + dy[dir]), dir));
dist[x + dx[dir]][y + dy[dir]] = dist[x][y] + 1;
cnt ++;
}
dir ++;
dir %= 8;*/
}
}
}
int main()
{
in >> n >> m;
in >> xs >> ys >> xf >> yf;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
in >> a[i][j];
}
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
dist[i][j] = INF;
}
}
for(int i = 0; i < 7; i ++)
{
q[0].push(std :: make_pair(std :: make_pair(xs, ys), i));
cnt ++;
}
dist[xs][ys] = 0;
dial();
/*for(int i = 1; i <= n; i ++, out << '\n')
{
for(int j = 1; j <= m; j ++)
{
out << dist[i][j] << " ";
}
}*/
if(dist[xf][yf] == INF)
{
out << -1;
}
else
{
out << dist[xf][yf];
}
return 0;
}