Cod sursa(job #2413282)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 23 aprilie 2019 11:22:25
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 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];
//int idq[9][DIMN][DIMN];
char buff[2500000];
int poz;
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;
}
inline int getnr(){
    int nr=0;
    while (buff[poz]<'0' || buff[poz]>'9' )
        poz++;
    while ('0'<=buff[poz] && buff[poz]<='9'){
        nr=nr*10+(buff[poz]-'0');
        poz++;
    }
    return nr;
}
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;
    fread (buff,1,2500000,fin);
    n=getnr();
    m=getnr();
    ist=getnr();
    jst=getnr();
    isf=getnr();
    jsf=getnr();
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)
            a[i][j]=getnr();
    }
    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==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;
}