Pagini recente » Cod sursa (job #2036244) | Cod sursa (job #2336481) | Cod sursa (job #1545066) | Cod sursa (job #2245825) | Cod sursa (job #2847736)
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
const ll NMAX = 501 * 501 * 8;
const ll VMAX = 21;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 31;
const ll nr_of_bits = 21;
vector <int> v[NMAX];
vector <pii> g[NMAX];
int dp[NMAX];
int viz[NMAX];
int mat[501][501];
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
int ind[501][501][8];
int n, m;
bool OK(int i, int j){
if(i < 1 || i > n || j < 1 || j > m)
return false;
return (mat[i][j] == 0);
}
int main() {
ifstream cin("car.in");
ofstream cout("car.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i, j, si, sj, fi, fj;
cin >> n >> m >> si >> sj >> fi >> fj;
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++)
cin >> mat[i][j];
}
if(mat[si][sj] == 1){
cout << -1;
return 0;
}
int cnt = 0;
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
for(int d = 0; d < 8; d++){
ind[i][j][d] = ++cnt;
dp[cnt] = 1e9;
}
}
}
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
if(mat[i][j] == 1)
continue;
for(int d = 0; d < 8; d++){
int nod = ind[i][j][d];
for(int d1 = 0; d1 < 8; d1++){
int ni = i + dx[d1];
int nj = j + dy[d1];
if(!OK(ni, nj))
continue;
int nou = ind[ni][nj][d1];
int cost = max(dx[d], dx[d1]) - min(dx[d], dx[d1]) + max(dy[d], dy[d1]) - min(dy[d], dy[d1]);
g[nod].push_back({nou, cost});
}
}
}
}
int goodL = ind[fi][fj][0];
int goodR = ind[fi][fj][7];
for(int i = 0; i < 7; i++){
dp[ind[si][sj][i]] = 0;
v[0].push_back(ind[si][sj][i]);
}
int act = 0;
while(act < NMAX){
//debug(act);
while(v[act].size()){
int x = v[act].back();
v[act].pop_back();
if(goodL <= x && x <= goodR){
cout << act << "\n";
return 0;
}
if(viz[x])
continue;
//debug(x);
viz[x] = 1;
for(auto y : g[x]){
if(dp[y.first] > y.second + dp[x]){
dp[y.first] = y.second + dp[x];
v[dp[y.first]].push_back(y.first);
}
}
}
act++;
}
cout << -1;
return 0;
}