Cod sursa(job #2950715)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 4 decembrie 2022 16:09:47
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int n,m,xs,ys,rezultat=1e9,xf,yf;
int a[501][501][8],b[501][501];
int dx[]= {1,1,0,-1,-1,-1,0,1};
int dy[]= {0,-1,-1,-1,0,1,1,1};
struct nod
{
    int x,y,dir;
};
int costuri[8][8]=
{
    0, 1, 2, 3, 4, 3, 2, 1,
    1, 0, 1, 2, 3, 4, 3, 2,
    2, 1, 0, 1, 2, 3, 4, 5,
    3, 2, 1, 0, 1, 2, 3, 4,
    4, 3, 2, 1, 0, 1, 2, 3,
    3, 4, 3, 2, 1, 0, 1, 2,
    2, 3, 4, 3, 2, 1, 0, 1,
    1, 2, 3, 4, 3, 2, 1, 0
};
queue<nod>st;
int main()
{
    f>>n>>m;
    f>>xs>>ys>>xf>>yf;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f>>b[i][j];
    for(int i=0; i<=n+1; i++)
        b[i][0]=b[i][n+1]=b[n+1][i]=b[0][i]=-1;
    for(int i=0; i<8; i++)
        if(!b[xs+dx[i]][ys+dy[i]])
            st.push(nod{xs,ys,i}),a[xs][ys][i]=1;
    while(st.size())
    {
        int X=st.front().x;
        int Y=st.front().y;
        int d=st.front().dir;
        st.pop();
        int x1=X+dx[d];
        int y1=Y+dy[d];
        for(int i=0; i<8; i++)
        {
            int cost=costuri[d][i];
            int XX=x1+dx[i];
            int YY=y1+dy[i];
            if(XX==xf&&YY==yf)
                rezultat=min(rezultat,a[X][Y][d]+cost);
            if(!b[XX][YY])
                if(a[x1][y1][i]>a[X][Y][d]+cost||(!a[x1][y1][i]))
                    st.push(nod{x1,y1,i}),a[x1][y1][i]=a[X][Y][d]+cost;

        }
    }
    g<<rezultat-1;
    return 0;
}