Cod sursa(job #2413276)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 23 aprilie 2019 11:18:55
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <deque>
#include <algorithm>
#define DIMN 501
using namespace std;
int a[DIMN][DIMN], d[9][DIMN][DIMN],f[9][DIMN][DIMN];
deque < pair <pair <int,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 (i=1;i<=8;i++){
        d[i][ist][jst]=1;
        f[i][ist][jst]=1;
        dq.push_back(make_pair(make_pair(ist,jst),i));
    }
    while (!dq.empty()){
        ic=dq.front().first.first;
        jc=dq.front().first.second;
        dir = dq.front().second;
        dq.pop_front();
        //if (ic==3 && jc==5 && dir==1)
          //  printf ("%d",d[dir][ic][jc]);

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

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

            f[dir][iv][jv]=1;
            d[dir][iv][jv] = d[dir][ic][jc];
            dq.push_back(make_pair(make_pair(iv,jv),dir));

            iv += di[dir];
            jv += dj[dir];
        }


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

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