Cod sursa(job #3254716)

Utilizator TonyyAntonie Danoiu Tonyy Data 8 noiembrie 2024 17:08:07
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 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 = 501;
vector<vector<int>> a(Max, vector<int>(Max)), c(Max, vector<int>(Max, INT_MAX));
queue<pair<int,int>> q;

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 && (y0 == y2 + 2 || y0 == y2 - 2))
    {
        if(x1 == x2)
            return 0;
        return 2;
    }
    if(y0 == y2 && (x0 == x2 + 2 || x0 == x2 - 2))
    {
        if(y1 == y2)
            return 0;
        return 2;
    }
    if(x0 - x2 == y0 - y2 || x0 + x2 == y0 + y2)
        return 0;
    if((x0 == x1 && x1 != x2) || (y0 == y1 && y1 != y2) || (x2 == x1 && x1 != x0) || (y2 == y1 && y1 != y0))
        return 1;
    return -1;
}

void lee(int x, int y)
{
    int old_x = 1, old_y = 1;
    c[x][y] = 0;
    q.push({x, y});
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        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;
                q.push({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];

    c[s1][s2] = 0;
    for(int d = 0; d < 8; ++d)
    {
        int x = s1 + dx[d];
        int y = s2 + dy[d];
        if(verify(x, y))
            lee(x, y);
    }
    fout << c[f1][f2];
    /*
    for(int i = 1; i <= n; ++i, fout << "\n")
        for(int j = 1; j <= m; ++j)
            if(c[i][j] != INT_MAX)
                fout << c[i][j] << " ";
            else
                fout << "* ";
    */
    fin.close();
    fout.close();
    return 0;
}