Pagini recente » Cod sursa (job #382855) | Cod sursa (job #487512) | Cod sursa (job #2168512) | Cod sursa (job #1356109) | Cod sursa (job #2451020)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
const int maxn = 505;
int dp[maxn][maxn][10];
int M[maxn][maxn];
int n, m;
const int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1};
const int dy[] = { 0, 1, 1, 1, 0,-1,-1,-1};
struct muchie
{
int x, y;
int dir, cost;
};
queue <muchie> q1;
queue <muchie> q2;
bool inside(int x, int y)
{
if(x >= 1 && y >= 1 && x <= n && y <= m && M[x][y] == 0)
return 1;
return 0;
}
int main()
{
pair <int, int> p1;
pair <int, int> p2;
in >> n >> m >> p1.first >> p1.second >> p2.first >> p2.second;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
in >> M[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
for(int dir = 0; dir < 8; dir++)
dp[i][j][dir] = (1 << 30);
for(int dir = 0; dir < 8; dir++)
q1.push({p1.first, p1.second, dir, 0});
while(!q1.empty())
{
while(!q1.empty())
{
muchie p = q1.front();
q1.pop();
muchie nou = {p.x + dx[p.dir], p.y + dy[p.dir], p.dir, p.cost};
if(inside(nou.x, nou.y) && dp[nou.x][nou.y][nou.dir] > nou.cost)
{
dp[nou.x][nou.y][nou.dir] = nou.cost;
q1.push(nou);
}
nou.x = p.x;
nou.y = p.y;
nou.cost++;
nou.dir = (nou.dir + 1) % 8;
if(inside(nou.x, nou.y) && dp[nou.x][nou.y][nou.dir] > nou.cost)
{
dp[nou.x][nou.y][nou.dir] = nou.cost;
q2.push(nou);
}
nou.dir = p.dir - 1;
if(nou.dir < 0)
nou.dir = 7;
if(inside(nou.x, nou.y) && dp[nou.x][nou.y][nou.dir] > nou.cost)
{
dp[nou.x][nou.y][nou.dir] = nou.cost;
q2.push(nou);
}
}
while(!q2.empty())
{
muchie p = q2.front();
q2.pop();
q1.push(p);
}
}
int mn = (1 << 30);
for(int dir = 0; dir < 8; dir++)
mn = min(mn, dp[p2.first][p2.second][dir]);
/*
for(int i = 1; i <= n; i++, cerr << "\n")
for(int j = 1; j <= m; j++, cerr << "\n")
for(int dir = 0; dir < 8; dir++)
cerr << dp[i][j][dir] << " ";
*/
if(mn == (1 << 30))
out << -1;
else
out << mn;
out << "\n";
return 0;
}