Pagini recente » Cod sursa (job #3322993) | Cod sursa (job #3353373) | Cod sursa (job #3309687) | Cod sursa (job #3136003) | Cod sursa (job #3321071)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
#if 0
#define int ll
#define uint ull
#endif
int dirl[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
dirc[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void tc() {
int n, m; cin >> n >> m;
int si, sj, fi, fj; cin >> si >> sj >> fi >> fj;
vector<vector<int>> mat(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> mat[i][j];
}
}
vector<vector<vector<int>>> minn(n + 1, vector<vector<int>>(m + 1, vector<int>(8, INT32_MAX)));
queue<tuple<int, int, int>> q;
for (int dir = 0; dir < 8; dir ++) {
minn[si][sj][dir] = 0;
q.push({si, sj, dir});
}
while (!q.empty()) {
auto [x, y, dir] = q.front(); q.pop();
for (int dir2 = 0; dir2 < 8; dir2 ++) {
int xx = x + dirl[dir2], yy = y + dirc[dir2];
// cout << min((dir - dir2 + 8) % 8, (dir2 - dir + 8) % 8) << " for " << dir << " -> " << dir2 << '\n';
if (1 <= xx && xx <= n && 1 <= yy && yy <= m && !mat[xx][yy] &&
minn[x][y][dir] + min((dir - dir2 + 8) % 8, (dir2 - dir + 8) % 8) < minn[xx][yy][dir2]
) {
minn[xx][yy][dir2] = minn[x][y][dir] + min((dir - dir2 + 8) % 8, (dir2 - dir + 8) % 8);
q.push({xx, yy, dir2});
}
}
}
cout << *min_element(minn[fi][fj].begin(), minn[fi][fj].end()) << '\n';
}
#define MTC 0
#define FIO 1
#define FN "car"
signed main() {
#if FIO == 1 && !defined(LOCAL)
(void)freopen(FN ".in", "r", stdin);
(void)freopen(FN ".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#if MTC == 1
signed tt; cin >> tt;
while (tt --) tc();
#else
tc();
#endif
return 0;
}