Cod sursa(job #1766531)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 septembrie 2016 00:08:28
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <cstdio>
#include <deque>

using namespace std;

const int kMaxN = 505;
const int kSize = 1 << 17;
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, cursor;
int v[kMaxN][kMaxN];
int d[kMaxN][kMaxN][8];
char buffer[kSize];
deque <pair <pair <int, int>, char>> dq;

void readInt(int &v) {
    v = 0;
    while (buffer[cursor] < '0' || '9' < buffer[cursor]) {
        cursor++;
        if (cursor == kSize) {
            cursor = 0;
            fread(buffer, kSize, 1, stdin);
        }
    }
    while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
        v = (v << 1) + (v << 3) + buffer[cursor] - '0';
        cursor++;
        if (cursor == kSize) {
            cursor = 0;
            fread(buffer, kSize, 1, stdin);
        }
    }
}

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);
    
    cursor = 0;
    fread(buffer, kSize, 1, stdin);
    
    readInt(n); 
    readInt(m);
    readInt(xs);
    readInt(ys);
    readInt(xe);
    readInt(ye);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            readInt(v[i][j]);
        }
    }
    printf("%d\n", findPath());
    
    return 0;
}