Cod sursa(job #1766525)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 septembrie 2016 23:58:27
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 505;
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n, m, xs, ys, xe, ye;
bool v[kMaxN][kMaxN];
int d[kMaxN][kMaxN][8];
deque <pair <pair <int, int>, char>> dq;

int findPath() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < 8; k++) {
                d[i][j][k] = 0x3f3f3f3f;
            }
        }
    }
    for (int i = 0; i <= n + 1; i++) {
        v[i][0] = v[i][m + 1] = 1;
    }
    for (int i = 0; i <= m + 1; i++) {
        v[0][i] = v[n + 1][i] = 1;
    }
    for (int i = 0; i < 8; i++) {
        d[xs][ys][i] = 0;
        dq.push_front({{xs, ys}, i});
    }
    while (!dq.empty()) {
        int x = dq.front().first.first;
        int y = dq.front().first.second;
        int dir = dq.front().second;
        dq.pop_front();
        if (x == xe && y == ye) {
            return d[x][y][dir];
        }
        int nx[3] = {x, x, x + dx[dir]};
        int ny[3] = {y, y, y + dy[dir]};
        int ndir[3] = {(dir - 1 + 8) & 7, (dir + 1) & 7, dir};
        int ncost[3] = {d[x][y][dir] + 1, d[x][y][dir] + 1, d[x][y][dir]};
        for (int i = 0; i < 3; i++) {
            if (!v[nx[i]][ny[i]] && d[nx[i]][ny[i]][ndir[i]] > ncost[i]) {
                d[nx[i]][ny[i]][ndir[i]] = ncost[i];
                if (i == 2) {
                    dq.push_front({{nx[i], ny[i]}, ndir[i]});
                }
                else {
                    dq.push_back({{nx[i], ny[i]}, ndir[i]});
                }
            }
        }
    }
    return -1;
}

int main() {
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &xs, &ys, &xe, &ye);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &v[i][j]);
        }
    }
    printf("%d\n", findPath());
    return 0;
}