Cod sursa(job #2837011)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 ianuarie 2022 14:58:30
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int maxN = 505, inf = 0x3f3f3f3f;
int dlin[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dcol[] = {0, 1, 1, 1, 0, -1, -1, -1};

struct pozitie{
    int i, j, dir, cost;
};

queue <pozitie> q0, q1;
int n, m, x1, y1, x2, y2, dp[maxN][maxN][10];
bool mat[maxN][maxN];

bool InBounds(int x, int y)
{
    return 0 < x && 0 < y && x <= n && y <= m && !mat[x][y];
}

void citire()
{
    fin >> n >> m >> x1 >> y1 >> x2 >> y2;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            fin >> mat[i][j];
            for(int k = 0; k < 8; k++)
                dp[i][j][k] = inf;
        }
    }
    for(int i = 0; i < 8; i++)
        q0.push({x1, y1, i, 0});
}

void bfs()
{
    pozitie nod, vecin;
    while(!q0.empty())
    {
        while(!q0.empty())
        {
            nod = q0.front();
            q0.pop();
            vecin.i = nod.i + dlin[nod.dir];
            vecin.j = nod.j + dcol[nod.dir];
            vecin.dir = nod.dir, vecin.cost = nod.cost;
            if (InBounds(vecin.i, vecin.j) && dp[vecin.i][vecin.j][vecin.dir] > vecin.cost)
            {
                dp[vecin.i][vecin.j][vecin.dir] = vecin.cost;
                q0.push(vecin);
            }
            vecin.cost++;
            vecin.dir = (vecin.dir + 1) % 8;
            vecin.i = nod.i;
            vecin.j = nod.j;
            if (InBounds(vecin.i, vecin.j) && dp[vecin.i][vecin.j][vecin.dir] > vecin.cost)
            {
                dp[vecin.i][vecin.j][vecin.dir] = vecin.cost;
                q1.push(vecin);
            }
            vecin.dir = nod.dir - 1;
            if (vecin.dir < 0)
                vecin.dir = 7;
            if (InBounds(vecin.i, vecin.j) && dp[vecin.i][vecin.j][vecin.dir] > vecin.cost)
            {
                dp[vecin.i][vecin.j][vecin.dir] = vecin.cost;
                q1.push(vecin);
            }
        }
        while(!q1.empty())
        {
            q0.push(q1.front());
            q1.pop();
        }
    }
}

void afis()
{
    int ans = inf;
    for(int i = 0; i < 8; i++)
        ans = min(ans, dp[x2][y2][i]);
    if(ans == inf)
        fout << -1;
    else
        fout << ans;
}

int main()
{
    citire();
    bfs();
    afis();
    return 0;
}