Pagini recente » Cod sursa (job #3321471) | Cod sursa (job #3349761) | Cod sursa (job #3313028) | Cod sursa (job #3320739) | Cod sursa (job #3327281)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int DI[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int DJ[] = { 0, 1, 1, 1, 0, -1, -1, -1};
int n, m, i, j, incI, incJ, sfI, sfJ;
int cost[502][502][8], rasp;
bool bloc[502][502];
static inline void Lee() {
queue<tuple<int, int, int>> q;
for(i = 0; i < 8; i++) {
cost[incI][incJ][i] = 0;
q.push(make_tuple(incI, incJ, i));
}
while(!q.empty()) {
int i, j, d;
tie(i, j, d) = q.front();
q.pop();
for(int dir = -3; dir < 4; dir++) {
int costAdd = (dir < 0 ? -dir : dir);
int dirCur = (dir + d + 8) % 8;
int in = i + DI[dirCur];
int jn = j + DJ[dirCur];
if(!bloc[in][jn] && (1 <= in && in <= n && 1 <= jn && jn <= m)) {
if(cost[in][jn][dirCur] == -1 || cost[in][jn][dirCur] > cost[i][j][d] + costAdd)
cost[in][jn][dirCur] = cost[i][j][d] + costAdd;
q.push({in, jn, dirCur});
}
}
}
}
int main() {
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n >> m;
fin >> incI >> incJ;
fin >> sfI >> sfJ;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
fin >> bloc[i][j];
for(int k = 0; k < 8; k++) {
cost[i][j][k] = -1;
}
}
}
Lee();
rasp = INT_MAX;
for(i = 0; i < 8; i++) {
if(cost[sfI][sfJ][i] != -1) rasp = min(rasp, cost[sfI][sfJ][i]);
}
fout << rasp;
return 0;
}