Pagini recente » Cod sursa (job #421543) | Cod sursa (job #1464705) | Cod sursa (job #1530129) | Cod sursa (job #676769) | Cod sursa (job #2847752)
#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;
struct ura {
int i, j, d;
};
int dp[501][501][8];
bitset <501> mat[501];
bool viz[501][501][8];
short dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
short dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
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++) {
int a;
cin >> a;
if(a == 1)
mat[i].flip(j);
}
}
if(mat[si][sj] == 1) {
cout << -1;
return 0;
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
for(int d = 0; d < 8; d++) {
dp[i][j][d] = 1e9;
}
}
} deque <ura> v;
for(int i = 0; i < 8; i++) {
dp[si][sj][i] = 0;
v.push_back({si, sj, i});
}
while(v.size()) {
ura x = v.front();
v.pop_front();
if(viz[x.i][x.j][x.d])
continue;
viz[x.i][x.j][x.d] = true;
int i = x.i;
int j = x.j;
int d = x.d;
for(int d1 = 0; d1 < 8; d1++) {
int ni = i + dx[d1];
int nj = j + dy[d1];
if(!OK(ni, nj))
continue;
ura nou = {ni, nj, d1};
int ceva = dp[i][j][d];
int cost = max(dx[d], dx[d1]) - min(dx[d], dx[d1]) + max(dy[d], dy[d1]) - min(dy[d], dy[d1]);
if(dp[ni][nj][d1] > cost + ceva) {
dp[ni][nj][d1] = cost + ceva;
if(d != d1)
v.push_back(nou);
else v.push_front(nou);
}
}
}
int minim = 1e9;
for(int i = 0; i < 8; i++){
minim = min(minim, dp[fi][fj][i]);
}
cout << minim;
return 0;
}