Cod sursa(job #2782060)

Utilizator marcumihaiMarcu Mihai marcumihai Data 11 octombrie 2021 15:59:08
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("car.in");
ofstream g ("car.out");

int mt[505][505];
int di[8]= {0,  0, 1,  1, -1, -1, 1, -1};
int dj[8]= {1, -1, 0, -1,  1,  0, 1, -1};
int mini[505][505];
int n, m ;

struct celula
{
    int lin;
    int col;
    int itata;
    int jtata;

    int cost;

    bool operator < (const celula &A) const
    {
        return cost>A.cost;
    }
};

priority_queue <celula> Q;

struct punct
{
    int i;
    int j;

};
double dist(punct a, punct b)
{
    return sqrt(abs(a.i-b.i)*abs(a.i-b.i)+abs(a.j-b.j)*abs(a.j-b.j));
}
int egal(punct a, punct b)
{
    if(a.i==b.i && a.j==b.j)
        return 1;
    return 0;
}
int gasire(punct prim, punct doi, punct trei)
{
    if(egal(prim, doi) || egal(trei, doi) || egal(prim, trei))
        return 9999999;
    if(abs(dist(prim, doi)+dist(doi, trei)-dist(prim, trei))<0.01)
        return 0;

    if(abs(dist(prim , trei)-sqrt(5))<0.01)
        return 1;


    if(abs(dist(prim, doi)*dist(prim, doi) + dist(doi, trei)*dist(doi, trei)-dist(prim, trei)*dist(prim, trei))<0.01 )
        return 2;

    if(abs(dist(prim, doi)*dist(prim, doi) + dist(prim, trei)*dist(prim, trei)-dist(trei, doi)*dist(trei, doi))<0.01 )
        return 1;
    if(abs(dist(trei, doi)*dist(trei, doi) + dist(prim, trei)*dist(prim, trei)-dist(prim, doi)*dist(prim, doi))<0.01 )
        return 1;

    return 99999999;

}

int ok(int i, int j)
{
    if(i<=0 || j<=0 || i>n || j>m)
        return 0;
    if(mt[i][j]==1)
        return 0;
    return 1;

}

void Dijkstra(int x, int y)
{

    for(int i=0; i<8; ++i)
        if(ok(x+di[i], y+dj[i]))
        {
            Q.push({x+di[i], y+dj[i], x, y, 0});
            mini[x+di[i]][y+dj[i]]=0;
        }
    while(!Q.empty())
    {
        int i=Q.top().lin;
        int j=Q.top().col;
        int itata=Q.top().itata;
        int jtata=Q.top().jtata;
        int cost=Q.top().cost;

        for(int x=0; x<8; ++x)
        {
            if(ok(i+di[x], j+dj[x]))
            {
                punct prim= {itata, jtata};
                punct secund= {i, j};
                punct trei= {i+di[x],  j+dj[x]};
                cost=gasire(prim, secund, trei);
                if(mini[i+di[x]][j+dj[x]]>mini[i][j]+cost)
                {
                    Q.push({i+di[x], j+dj[x], i, j, mini[i][j]+cost});
                    mini[i+di[x]][j+dj[x]]=mini[i][j]+cost;
                }
            }
        }
        Q.pop();
    }
}

int main()
{
    f>>n>>m;
    int istart, jstart, ifin, jfin;

    f>>istart>>jstart>>ifin>>jfin;

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)

            mini[i][j]=999999;

    mini[istart][jstart]=0;

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            f>>mt[i][j];

    Dijkstra(istart, jstart);

    g<<mini[ifin][jfin];

    return 0;
}