Pagini recente » Cod sursa (job #1712297) | Cod sursa (job #1400997) | Cod sursa (job #2712317) | Cod sursa (job #923335) | Cod sursa (job #2922634)
#include <bits/stdc++.h>
#define NMAX 500
#define INFINIT 2000000 //doua milioane = 500 * 500 * 8
/*
0 1 2
7 3
6 5 4
*/
using namespace std;
ifstream fin ("test.in");
ofstream fout ("test.out");
struct elem{
int x, y, dir;
};
int N, M;
int Si, Sj, Fi, Fj;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int v[NMAX + 1][NMAX + 1];
int dp[NMAX + 2][NMAX + 2][8];
deque <elem> Q;
void Solve(){
for(int i = 0; i <= 7; i++){
Q.push_back(elem{Si, Sj, i});
dp[Si][Sj][i] = 0;
}
while(!Q.empty()){
int x = Q.front().x;
int y = Q.front().y;
int dir = Q.front().dir;
Q.pop_front();
int xn = x + dx[dir];
int yn = y + dy[dir];
if(v[xn][yn] == 0 && dp[x][y][dir] < dp[xn][yn][dir]){
dp[xn][yn][dir] = dp[x][y][dir];
Q.push_front(elem{xn, yn, dir});
}
int dir1 = (dir - 1 + 8) % 8;
int dir2 = (dir + 1) % 8;
if(dp[x][y][dir] + 1 < dp[x][y][dir1]){
dp[x][y][dir1] = dp[x][y][dir] + 1;
Q.push_back(elem{x, y, dir1});
}
if(dp[x][y][dir] + 1 < dp[x][y][dir2]){
dp[x][y][dir2] = dp[x][y][dir] + 1;
Q.push_back(elem{x, y, dir2});
}
}
}
int main()
{
fin >> N >> M;
fin >> Si >> Sj >> Fi >> Fj;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
fin >> v[i][j];
}
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
for(int k = 0; k <= 7; k++){
dp[i][j][k] = INFINIT;
}
}
}
Solve();
int rez = INFINIT;
for(int k = 0; k <= 7; k++){
rez = min(rez, dp[Fi][Fj][k]);
}
if(rez == INFINIT){
fout << -1 << "\n";
}
else {
fout << rez << "\n";
}
return 0;
}