Cod sursa(job #2649984)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 16 septembrie 2020 23:44:59
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <bits/stdc++.h>

using namespace std;

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

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

/*
 4 - 5 - 6
 3 - x - 7
 2 - 1 - 0
*/

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

queue<pair<int /*-cost*/, pair<int, int> /*poz*/>> pq;

int abs(int x) {
    return max(x, -x);
}

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 <= m; j++)
        {
            in >> mat[i][j];
        }
    }

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    for(int dir = 0; dir < 8; dir++)
        viz[i][j][dir] = 1000000000;

    for(int dir = 0; dir < 8; dir++)
    {
        viz[x1][y1][dir] = 0;
        pq.push(make_pair(-0, make_pair(x1, y1)));
    }

    bool touched = 0;

    while(!touched && !pq.empty())
    {
        auto cnt = pq.front(); pq.pop();

        if(cnt.second.first == x2 && cnt.second.second == y2)
            touched = 1;

        for(int dir = 0; dir < 8; dir++)
        {
            for(int chdir = -3; chdir <= 4; chdir++)
            {
                int new_x, new_y, new_dir;
                new_dir = (dir + 8 + chdir) % 8;
                new_x = cnt.second.first + dx[new_dir];
                new_y = cnt.second.second + dy[new_dir];

                if(mat[new_x][new_y] == 0 && viz[new_x][new_y][new_dir] > viz[cnt.second.first][cnt.second.second][dir] + abs(chdir))
                {
                    viz[new_x][new_y][new_dir] = viz[cnt.second.first][cnt.second.second][dir] + abs(chdir);
                    pq.push(make_pair(-(viz[cnt.second.first][cnt.second.second][dir] + abs(chdir)), make_pair(new_x, new_y)));
                }
            }
        }
    }

    //cout << viz[4][4][6] << endl;

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

    out << minim;
}