Cod sursa(job #3312136)

Utilizator CalinPaun29Paun Calin CalinPaun29 Data 26 septembrie 2025 11:23:32
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
//#pragma GCC optimize("O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int mat[505][505];
int mat2[505][505][8];
int d1[]={-1, -1, 0, 1, 1, 1, 0, -1};
int d2[]={0, 1, 1, 1, 0, -1, -1, -1};
struct stare
{
    int fi, se, dir;
};
signed main()
{
    ifstream cin("car.in");
    ofstream cout("car.out");
    int n, m, a1, a2, b1, b2, mincnt=1000000;
    cin>>n>>m;
    cin>>a1>>b1>>a2>>b2;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>mat[i][j];
            for(int k=0; k<=7; k++)
                mat2[i][j][k]=1000000;
        }
    }
    queue<stare> q[3];
    for(int j=0;j<7;j++)
    {
        //if(a1+d1[j]>0 && a1+d1[j]<=n && b1+d2[j]>0 && b1+d2[j]<=m && mat[a1+d1[j]][b1+d2[j]]==0)
       // {
            mat2[a1][b1][j]=0;
            q[0].push({a1, b1, j});
        //}
    }
    for(int i=0; i<n*m*4; i++)
    {
        while(!q[i%3].empty())
        {
            int x=q[i%3].front().fi, y=q[i%3].front().se, z=q[i%3].front().dir;
            q[i%3].pop();
            if(x==a2 && y==b2)
            {
                if(mincnt>i)
                    mincnt=i;
            }
            for(int j=-2;j<=2;j++)
            {
                int xx=z+j;
                if(xx<0)
                    xx+=8;
                else if(xx>7)
                    xx-=8;

                if(x+d1[xx]>0 && x+d1[xx]<=n && y+d2[xx]>0 && y+d2[xx]<=m && mat[x+d1[xx]][y+d2[xx]]==0 && mat2[x+d1[xx]][y+d2[xx]][xx]>mat2[x][y][z]+max(j, (-1)*j))
                {
                    mat2[x+d1[xx]][y+d2[xx]][xx]=mat2[x][y][z]+max(j, (-1)*j);
                    q[(i+max(j, (-1)*j))%3].push({x+d1[xx], y+d2[xx], xx});
                }
            }
        }
    }
    cout<<mincnt;
    return 0;
}