Pagini recente » Cod sursa (job #2181157) | Cod sursa (job #646244) | Cod sursa (job #2955395) | Cod sursa (job #450411) | Cod sursa (job #2638609)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
struct triplet{
int x, y, dir;
};
int n, m, xx1, yy1, x2, y2, dp[505][505][8], matrix[505][505];
int dx[] = {-1, -1, 0, 1, -1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
deque <triplet> coada;
bool Valid(int i, int j)
{
return i >= 1 && j >= 1 && i <= n && j <= m && matrix[i][j] == 0;
}
int main(){
fin >> n >> m >> xx1 >> yy1 >> x2 >> y2;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
fin >> matrix[i][j];
}
}
for (int i = 0; i < 8; ++i){
coada.push_back({xx1, yy1, i});
dp[xx1][yy1][i] = 1;
}
while (!coada.empty()){
int x = coada.front().x;
int y = coada.front().y;
int dir = coada.front().dir;
coada.pop_front();
int dir2 = dir;
int xx = x + dx[dir2];
int yy = y + dy[dir2];
if (Valid(xx, yy) && dp[xx][yy][dir2] == 0){
dp[xx][yy][dir2] = dp[x][y][dir];
coada.push_front({xx, yy, dir2});
}
dir2 = (dir + 1) % 8;
xx = x;
yy = y;
if (Valid(xx, yy) && dp[xx][yy][dir2] == 0){
dp[xx][yy][dir2] = dp[x][y][dir] + 1;
coada.push_back({xx, yy, dir2});
}
dir2 = (dir + 7) % 8;
xx = x;
yy = y;
if (Valid(xx, yy) && dp[xx][yy][dir2] == 0){
dp[xx][yy][dir2] = dp[x][y][dir] + 1;
coada.push_back({xx, yy, dir2});
}
}
int minim = 1e9;
for (int i = 0; i < 8; ++i){
if (dp[x2][y2][i] == 0) continue;
minim = min(minim, dp[x2][y2][i]);
}
if (minim == 1e9){
minim = -1;
}
fout << minim - 1;
fin.close();
fout.close();
return 0;
}