Cod sursa(job #3254693)

Utilizator TonyyAntonie Danoiu Tonyy Data 8 noiembrie 2024 15:32:21
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

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

const vector<int> dx({-1, -1, -1, 0, 0, 1, 1, 1});
const vector<int> dy({-1, 0, 1, -1, 1, -1, 0, 1});

int n, m;
const int Max = 6;
vector<vector<int>> a(Max, vector<int>(Max)), c(Max, vector<int>(Max, INT_MAX));
vector<vector<bool>> v(Max, vector<bool>(Max));

bool verify(int x, int y)
{
    return x >= 1 && y >= 1 && x <= n && y <= m && !a[x][y];
}

int turn_cost(int x0, int y0, int x1, int y1, int x2, int y2)
{
    if(x0 == x2)
    {
        if(x1 == x2)
            return 0;
        return 2;
    }
    if(y0 == y2)
    {
        if(y1 == y2)
            return 0;
        return 2;
    }
    if((x0 == x1 && x1 != x2) || (y0 == y1 && y1 != y2) || (x2 == x1 && x1 != x0) || (y2 == y1 && y1 != y0))
        return 1;
    if(x0 - x2 == y0 - y2 || x0 + x2 == y0 + y2)
        return 0;
    return -1;
}

void lee(int x, int y)
{
    deque<pair<int,int>> q;
    int old_x = x, old_y = y;
    c[x][y] = 0;
    v[x][y] = true;
    for(int d = 0; d < 8; ++d)
    {
        int new_x = x + dx[d];
        int new_y = y + dy[d];
        if(verify(new_x, new_y))
        {
            c[new_x][new_y] = 0;
            q.push_back({new_x, new_y});
        }
    }
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop_front();
        if(v[x][y])
            continue;
        v[x][y] = true;
        for(int d = 0; d < 8; ++d)
        {
            int new_x = x + dx[d];
            int new_y = y + dy[d];
            int cost = turn_cost(old_x, old_y, x, y, new_x, new_y);
            if(cost == -1)
                continue;
            if(verify(new_x, new_y) && c[x][y] + cost < c[new_x][new_y])
            {
                c[new_x][new_y] = c[x][y] + cost;
                old_x = x;
                old_y = y;
                if(!cost)
                    q.push_front({new_x, new_y});
                else
                    q.push_back({new_x, new_y});
            }
        }
    }
}

int main()
{
    int s1, s2, f1, f2;
    fin >> n >> m >> s1 >> s2 >> f1 >> f2;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            fin >> a[i][j];

    lee(s1, s2);
    fout << c[f1][f2];

    fin.close();
    fout.close();
    return 0;
}