Pagini recente » Cod sursa (job #3131836) | Cod sursa (job #3132228) | Cod sursa (job #376287) | Cod sursa (job #1018523) | Cod sursa (job #3254703)
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin ("car.in");
ofstream fout("car.out");
const vector<int> dx({-1, -1, -1, 0, 0, 1, 1, 1});
const vector<int> dy({-1, 0, 1, -1, 1, -1, 0, 1});
int n, m, s1, s2, f1, f2;;
const int Max = 501;
vector<vector<int>> a(Max, vector<int>(Max)), c(Max, vector<int>(Max, INT_MAX));
vector<vector<bool>> v(Max, vector<bool>(Max));
bool verify(int x, int y)
{
return x >= 1 && y >= 1 && x <= n && y <= m && !a[x][y];
}
int turn_cost(int x0, int y0, int x1, int y1, int x2, int y2)
{
if(x0 == x2 && (y0 == y2 + 2 || y0 == y2 - 2))
{
if(x1 == x2)
return 0;
return 2;
}
if(y0 == y2 && (x0 == x2 + 2 || x0 == x2 - 2))
{
if(y1 == y2)
return 0;
return 2;
}
if((x0 == x1 && x1 != x2) || (y0 == y1 && y1 != y2) || (x2 == x1 && x1 != x0) || (y2 == y1 && y1 != y0))
return 1;
if((x0 - x2 == y0 - y2 || x0 + x2 == y0 + y2) && (y0 == y2 + 2 || y0 == y2 - 2|| x0 == x2 + 2 || x0 == x2 - 2))
return 0;
return -1;
}
void lee(int x, int y)
{
queue<pair<int,int>> q;
int old_x = x, old_y = y;
c[x][y] = 0;
v[x][y] = true;
for(int d = 8; d >= 0; --d)
{
int new_x = x + dx[d];
int new_y = y + dy[d];
if(verify(new_x, new_y))
{
c[new_x][new_y] = 0;
q.push({new_x, new_y});
}
}
while(!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
if(v[x][y])
continue;
v[x][y] = true;
if((x == s1 - 1 && (y == s2 - 1 || y == s2 || y == s2 + 1)) || (x == s1 && (y == s2 - 1 || y == s2 || y == s2 + 1)) || (x == s1 + 1 && (y == s2 - 1 || y == s2 || y == s2 + 1)))
old_x = old_y = 1;
for(int d = 0; d < 8; ++d)
{
int new_x = x + dx[d];
int new_y = y + dy[d];
int cost = turn_cost(old_x, old_y, x, y, new_x, new_y);
if(cost == -1)
continue;
if(verify(new_x, new_y) && c[x][y] + cost < c[new_x][new_y])
{
c[new_x][new_y] = c[x][y] + cost;
old_x = x;
old_y = y;
q.push({new_x, new_y});
}
}
}
}
int main()
{
fin >> n >> m >> s1 >> s2 >> f1 >> f2;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
fin >> a[i][j];
lee(s1, s2);
fout << c[f1][f2];
/*
for(int i = 1; i <= n; ++i, fout << "\n")
for(int j = 1; j <= m; ++j)
if(c[i][j] != INT_MAX)
fout << c[i][j] << " ";
else
fout << "* ";
*/
fin.close();
fout.close();
return 0;
}