Cod sursa(job #2493851)

Utilizator GhSamuelGherasim Teodor-Samuel GhSamuel Data 17 noiembrie 2019 01:17:57
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
#define Nmax 550
using namespace std;
ifstream f("car.in");
ofstream g("car.out");

int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, xs, ys, xf, yf, dist[Nmax][Nmax][8];
bool mat[Nmax][Nmax];

struct point {
    int x, y, dir, cost;
};

deque <point> Coada;

void read()
{
    f >> n >> m >> xs >> ys >> xf >> yf;
    --xs; --ys; --xf; --yf;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
        f >> mat[i][j];
    }
}

void solve()
{
    if (mat[xs][ys] == 1 || mat[xf][yf] == 1) {
        g << "-1";
        return;
    }
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
    for (int k = 0; k < 8; ++k) {
        dist[i][j][k] = INT_MAX;
    }

    for (int i = 0; i < 8; ++i) {
        dist[xs][ys][i] = 0;
        Coada.push_back({xs, ys, i, 0});
    }

    int trans[8][3];
    for (int i = 0; i < 8; ++i)
    for (int j = 0; j < 3; ++j) {
        trans[i][j] = (7 + i + j) % 8;
    }

    point pos;
    while (!Coada.empty()) {
        pos = Coada.front();
        Coada.pop_front();

        if (pos.cost > dist[pos.x][pos.y][pos.dir]) continue;

        for (int i = 0; i < 3; ++i) {
            int xn = pos.x + dx[trans[pos.dir][i]];
            int yn = pos.y + dy[trans[pos.dir][i]];
            int cost = (i != 1) + pos.cost;

            if (cost < dist[pos.x][pos.y][trans[pos.dir][i]]) {
                dist[pos.x][pos.y][trans[pos.dir][i]] = cost;
                Coada.push_back({pos.x, pos.y, trans[pos.dir][i], cost});
            }

            if (xn == -1 || yn == -1 || xn == n || yn == m || mat[xn][yn]) continue;

            if (cost < dist[xn][yn][trans[pos.dir][i]]) {
                dist[xn][yn][trans[pos.dir][i]] = cost;
                if (i == 1)
                    Coada.push_front({xn, yn, trans[pos.dir][i], cost});
                else
                    Coada.push_back({xn, yn, trans[pos.dir][i], cost});

            }
        }
    }

    int small = INT_MAX;
    for (int i = 0; i < 8; ++i)
        small = min(small, dist[xf][yf][i]);
    if (small == INT_MAX)
        g << "-1";
    else
        g << small;

}
int main()
{
    read();
    solve();
    return 0;
}