Cod sursa(job #2413270)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 23 aprilie 2019 11:10:45
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <cstdio>
#include <set>
#include <algorithm>
#define DIMN 501
#define INF 2000000000
using namespace std;
int a[DIMN][DIMN], d[9][DIMN][DIMN];
set < pair <pair <int,int>,pair <int,int> > > dq;
int di[] = {0, -1 , -1 , 0 , 1 , 1 , 1 , 0 , -1 };
int dj[] = {0, 0 , 1 , 1 , 1 , 0 , -1 , -1 , -1 };
inline int prev (int x){
    if (x-1>0)
        return x-1;
    return 8;
}
inline int nxt (int x){
    if (x+1<9)
        return x+1;
    return 1;
}
int main()
{
    FILE *fin=fopen ("car.in","r");
    FILE *fout=fopen ("car.out","w");
    int n,m,ist,jst,isf,jsf,i,j,dir,ic,jc,iv,jv;
    fscanf (fin,"%d%d%d%d%d%d",&n,&m,&ist,&jst,&isf,&jsf);
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)
            fscanf (fin,"%d",&a[i][j]);
    }
    for (dir=1;dir<=8;dir++){
        for (i=1;i<=n;i++){
            for (j=1;j<=m;j++)
                d[dir][i][j]=INF;
        }
    }
    for (i=1;i<=8;i++){
        d[i][ist][jst]=0;
        dq.insert(make_pair(make_pair(d[i][ist][jst],i),make_pair(ist,jst)));
    }
    while (!dq.empty()){
        ic=(*dq.begin()).second.first;
        jc=(*dq.begin()).second.second;
        dir =(*dq.begin()).first.second;
        dq.erase(dq.begin());

         //if (ic==2 && jc==2 && dir==4)
           // printf ("%d",d[dir][ic][jc]);

        if (ic==isf && jc==jsf){
            fprintf (fout,"%d ",d[dir][ic][jc]);
            return 0;
        }

        iv = ic + di[dir];
        jv = jc + dj[dir];
        while (iv && jv && iv<=n && jv<=m && a[iv][jv]==0 && d[dir][iv][jv] > d[dir][ic][jc]){

            if (d[dir][iv][jv] != INF){
                dq.erase(make_pair(make_pair(d[dir][iv][jv],dir),make_pair(iv,jv)));
            }
            d[dir][iv][jv] = d[dir][ic][jc];
            dq.insert(make_pair(make_pair(d[dir][iv][jv],dir),make_pair(iv,jv)));
            iv += di[dir];
            jv += dj[dir];
        }


        /// mutare cu 45 in spate
        if (d[prev(dir)][ic][jc] > 1 + d[dir][ic][jc]){
            if (d[prev(dir)][ic][jc]!=INF)
                dq.erase(make_pair(make_pair(d[prev(dir)][ic][jc],prev(dir)),make_pair(ic,jc)));
            d[prev(dir)][ic][jc] = 1 + d[dir][ic][jc];
            dq.insert(make_pair(make_pair(d[prev(dir)][ic][jc],prev(dir)),make_pair(ic,jc)));
        }

        /// mutare cu 45 in fata
        if (d[nxt(dir)][ic][jc] > 1 + d[dir][ic][jc]){
            if (d[nxt(dir)][ic][jc]!=INF)
                dq.erase(make_pair(make_pair(d[nxt(dir)][ic][jc],nxt(dir)),make_pair(ic,jc)));
            d[nxt(dir)][ic][jc] = 1 + d[dir][ic][jc];
            dq.insert(make_pair(make_pair(d[nxt(dir)][ic][jc],nxt(dir)),make_pair(ic,jc)));
        }
    }
    fprintf (fout,"-1");
    return 0;
}