Cod sursa(job #2649987)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 17 septembrie 2020 00:05:39
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("car.in");
ofstream out("car.out");

struct poz
{
    int x, y, dir;

    poz(int _x, int _y, int _dir)
    {
        x = _x; y = _y; dir = _dir;
    }
};

int dx[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dy[8] = {1, 0, -1, -1, -1, 0, 1, 1};

deque<poz> q;

int viz[505][505][8];
bool mat[505][505];

int main()
{
    int n, m; in >> n >> m;

    int x1, x2, y1, y2; in >> x1 >> y1 >> x2 >> y2;

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    {
        in >> mat[i][j];
        for(int dir = 0; dir < 8; dir++)
            viz[i][j][dir] = 1000000000;
    }

    for(int dir = 0; dir < 8; dir++) {
        q.push_back(poz(x1, y1, dir));
        viz[x1][y1][dir] = 0;
    }

    bool touched = 0;
    while(!touched && !q.empty())
    {
        poz cnt = q.front(); q.pop_front();

        if(cnt.x == x2 && cnt.y == y2) touched = 1;

        poz new_p(0, 0, 0);
        new_p.x = cnt.x + dx[cnt.dir];
        new_p.y = cnt.y + dy[cnt.dir];
        new_p.dir = cnt.dir;


        if(mat[new_p.x][new_p.y] == 0 && viz[new_p.x][new_p.y][new_p.dir] > viz[cnt.x][cnt.y][cnt.dir])
        {
            viz[new_p.x][new_p.y][new_p.dir] = viz[cnt.x][cnt.y][cnt.dir];
            q.push_front(new_p);
        }

        new_p.x = cnt.x;
        new_p.y = cnt.y;
        new_p.dir = (cnt.dir + 1) % 8;

        if(mat[new_p.x][new_p.y] == 0 && viz[new_p.x][new_p.y][new_p.dir] > viz[cnt.x][cnt.y][cnt.dir] + 1)
        {
            viz[new_p.x][new_p.y][new_p.dir] = viz[cnt.x][cnt.y][cnt.dir] + 1;
            q.push_back(new_p);
        }

        new_p.x = cnt.x;
        new_p.y = cnt.y;
        new_p.dir = (cnt.dir + 7) % 8;

        if(mat[new_p.x][new_p.y] == 0 && viz[new_p.x][new_p.y][new_p.dir] > viz[cnt.x][cnt.y][cnt.dir])
        {
            viz[new_p.x][new_p.y][new_p.dir] = viz[cnt.x][cnt.y][cnt.dir] + 1;
            q.push_back(new_p);
        }
    }

    int minim = viz[x2][y2][0];
    for(int dir = 0; dir < 8; dir++)
    {
        minim = min(minim, viz[x2][y2][dir]);
    }

    out << minim;
}