Pagini recente » Cod sursa (job #2570927) | Cod sursa (job #894447) | Cod sursa (job #2458627) | Cod sursa (job #2705961) | Cod sursa (job #1855391)
#include <cstdio>
#include <queue>
const int MAX_N = 500;
bool trec[1+MAX_N+1][1+MAX_N+1];
int dist[8][1+MAX_N+1][1+MAX_N+1];
const int INF = 1000000000;
struct Punct {
int l, c, dir;
};
std::queue<Punct> q;
int dl[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dc[] = {0,-1, -1,-1, 0, 1, 1, 1};
int main() {
int n, m, l1, c1, l2, c2;
FILE *fin = fopen("car.in", "r");
fscanf(fin, "%d%d%d%d%d%d", &n, &m, &l1, &c1, &l2, &c2);
for(int l = 1; l <= n; ++l)
for(int c = 1; c <= m; ++c) {
fscanf(fin, "%d", &trec[l][c]);
for(int i = 0; i < 8; ++i)
dist[i][l][c] = INF;
}
fclose(fin);
for(int i = 0; i < 8; ++i) {
dist[i][l1][c1] = 0;
q.push({l1, c1, i});
}
while(!q.empty()) {
int l = q.front().l;
int c = q.front().c;
int dir = q.front().dir;
q.pop();
for(int i = 0; i < 4; ++i) {
int dir2 = (dir + i) % 8;
int ln = l + dl[dir2];
int cn = c + dc[dir2];
if(1 <= ln && ln <= n && 1 <= cn && cn <= m)
if(!trec[ln][cn] && dist[dir][l][c] + i < dist[dir2][ln][cn]) {
dist[dir2][ln][cn] = dist[dir][l][c] + i;
q.push({ln, cn, dir2});
}
dir2 = (dir - i + 8) % 8;
ln = l + dl[dir2];
cn = c + dc[dir2];
if(1 <= ln && ln <= n && 1 <= cn && cn <= m)
if(!trec[ln][cn] && dist[dir][l][c] + i < dist[dir2][ln][cn]) {
dist[dir2][ln][cn] = dist[dir][l][c] + i;
q.push({ln, cn, dir2});
}
}
}
FILE *fout = fopen("car.out", "w");
int min = 1000000000;
for(int i = 0; i < 8; ++i)
if(dist[i][l2][c2] < min)
min = dist[i][l2][c2];
if(min == INF)
fprintf(fout, "-1");
else
fprintf(fout, "%d", min);
fclose(fout);
return 0;
}