Pagini recente » Cod sursa (job #3353290) | Cod sursa (job #989533) | Cod sursa (job #3352162) | Cod sursa (job #3355770) | Cod sursa (job #3327309)
#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 long long Encode(int i, int j, int d) {
return d + j * 10 + i * 10000;
}
static inline void Lee() {
queue<long long> q[3];
for(int dir = 0; dir < 8; dir++) {
cost[incI][incJ][dir] = 0;
q[0].push(Encode(incI, incJ, dir));
}
int coada = 0;
while(!q[0].empty() || !q[1].empty() || !q[2].empty()) {
while(q[coada].empty()) coada = (coada + 1) % 3;
int i = q[coada].front() / 10000 % 1000;
int j = q[coada].front() / 10 % 1000;
int d = q[coada].front() % 10;
q[coada].pop();
//cout << "! " << i << " " << j << " : " << d << "\n";
for(int rot = -2; rot <= 2; rot++) {
int costAdd = (rot < 0 ? -rot : rot);
int dir = (d + rot + 8) % 8;
int in = i + DI[dir];
int jn = j + DJ[dir];
if(!bloc[in][jn] && (1 <= in && in <= n && 1 <= jn && jn <= m)) {
if(cost[in][jn][dir] > cost[i][j][d] + costAdd) {
cost[in][jn][dir] = cost[i][j][d] + costAdd;
q[cost[in][jn][dir] % 3].push(Encode(in, jn, dir));
//cout << "+ " << cost[in][jn][dir] % 3 << " -> " << in << " " << jn << " : " << dir << "\n";
}
}
}
}
}
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] = INT_MAX;
}
}
}
Lee();
rasp = INT_MAX;
for(i = 0; i < 8; i++) {
if(cost[sfI][sfJ][i] != -1) rasp = min(rasp, cost[sfI][sfJ][i]);
}
if(rasp == INT_MAX) fout << "-1";
else fout << rasp;
return 0;
}