Cod sursa(job #2875970)

Utilizator bem.andreiIceman bem.andrei Data 22 martie 2022 19:02:26
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("car.in");
ofstream w("car.out");

const int inf = 0x3f3f3f3f;
struct poz
{
    int i, j, dir, cost;
};
queue<poz>q0, q1;
int n, m, a, b, c, d, dp[503][503][10], l[]={-1, -1, 0, 1, 1, 1, 0, -1}, col[]={0, 1, 1, 1, 0, -1, -1, -1};
bool mat[503][503];
bool ver(int x, int y)
{
    return 0<x&&0<y&&x<=n&&y<=m&&!mat[x][y];
}
void bfs()
{
    poz nod, urm;
    while(q0.size()!=0)
    {
        while(q0.size()!=0)
        {
            nod = q0.front();
            q0.pop();
            urm.i = nod.i + l[nod.dir];
            urm.j = nod.j + col[nod.dir];
            urm.dir = nod.dir, urm.cost = nod.cost;
            if (ver(urm.i, urm.j) && dp[urm.i][urm.j][urm.dir] > urm.cost)
            {
                dp[urm.i][urm.j][urm.dir] = urm.cost;
                q0.push(urm);
            }
            urm.cost++;
            urm.dir = (urm.dir + 1) % 8;
            urm.i = nod.i;
            urm.j = nod.j;
            if (ver(urm.i, urm.j) && dp[urm.i][urm.j][urm.dir] > urm.cost)
            {
                dp[urm.i][urm.j][urm.dir] = urm.cost;
                q1.push(urm);
            }
            urm.dir = nod.dir - 1;
            if (urm.dir < 0)
            {
                urm.dir = 7;
            }
            if (ver(urm.i, urm.j) && dp[urm.i][urm.j][urm.dir] > urm.cost)
            {
                dp[urm.i][urm.j][urm.dir] = urm.cost;
                q1.push(urm);
            }
        }
        while(!q1.empty())
        {
            q0.push(q1.front());
            q1.pop();
        }
    }
}
int main()
{
    r>>n>>m>>a>>b>>c>>d;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            r>>mat[i][j];
            for(int k = 0; k < 8; k++)
            {
                dp[i][j][k] = inf;
            }
        }
    }
    for(int i = 0; i < 8; i++)
    {
        q0.push({a, b, i, 0});
    }
    bfs();
    int ans = inf;
    for(int i = 0; i < 8; i++)
    {
        ans = min(ans, dp[c][d][i]);
    }
    if(ans == inf)
    {
        w<<-1;
    }
    else
    {
        w<<ans;
    }
    return 0;
}