Cod sursa(job #2413418)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 23 aprilie 2019 13:16:44
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <cstdio>
#include <deque>
#include <cstring>
#define DIM 510
#define DIMBUFF 5000000
using namespace std;

//ifstream fin ("car.in");
//ofstream fout ("car.out");
FILE *fin = fopen ("car.in","r");
FILE *fout = fopen ("car.out","w");
int n,m,i,j,ic,jc,iv,jv,dir,D,mini,istart,jstart,ifin,jfin,new_dir,poz;
deque < pair<pair<int,int>,int> > c;
int a[DIM][DIM],f[DIM][DIM][10],d[DIM][DIM][10];
int di[] = {-1,-1,0,1,1,1,0,-1};
int dj[] = {0,1,1,1,0,-1,-1,-1};
char buff[DIMBUFF];
inline bool inmat (int i, int j){
    if (i >= 1 && i <= n && j >= 1 && j <= m)
        return 1;
    return 0;
}
inline int get_nr(){
    while (!(buff[poz] >= '0' && buff[poz] <= '9'))
        poz++;
    int nr = 0;
    while (buff[poz] >= '0' && buff[poz] <= '9'){
        nr = nr*10 + buff[poz] - '0';
        poz++;
    }
    return nr;
}
int main (){

    //fin>>n>>m>>istart>>jstart>>ifin>>jfin;
    fread (buff,1,DIMBUFF,fin);
    n = get_nr(), m = get_nr();
    istart = get_nr(), jstart = get_nr();
    ifin = get_nr(), jfin = get_nr();
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            a[i][j] = get_nr();

    //memset (d,-1,sizeof(d));

    for (dir=0;dir<8;dir++){
        d[istart][jstart][dir] = f[istart][jstart][dir] = 1;
        c.push_back (make_pair(make_pair(istart,jstart),dir));
    }

    while (!c.empty()){
        ic = c.front().first.first;
        jc = c.front().first.second;
        dir = c.front().second; /// directia cu care intru in urm casuta
        c.pop_front();
        if (ic == ifin && jc == jfin){
            //fout<<d[ic][jc][dir]-1;
            fprintf(fout,"%d",d[ic][jc][dir]-1);
            return 0;
        }
        iv = ic + di[dir];
        jv = jc + dj[dir];
        while (inmat(iv,jv) && !a[iv][jv] && (d[iv][jv][dir] > d[ic][jc][dir] || !f[iv][jv][dir])){
            f[iv][jv][dir] = 1;
            d[iv][jv][dir] = d[ic][jc][dir]; /// nu imi schimb directia
            c.push_back (make_pair(make_pair(iv,jv),dir));
            iv = iv + di[dir];
            jv = jv + dj[dir];
        }

        new_dir = dir-1;
        if (new_dir < 0)
            new_dir = 7;

        if (!f[ic][jc][new_dir]){
            c.push_back (make_pair(make_pair(ic,jc),new_dir));
            d[ic][jc][new_dir] = 1 + d[ic][jc][dir];
            f[ic][jc][new_dir] = 1;
        }

        new_dir = dir+1;
        if (new_dir >= 8)
            new_dir = 0;

        if (!f[ic][jc][new_dir]){
            c.push_back (make_pair(make_pair(ic,jc),new_dir));
            d[ic][jc][new_dir] = 1 + d[ic][jc][dir];
            f[ic][jc][new_dir] = 1;
        }

    }

    //fout<<-1;
    fprintf(fout,"-1");

    return 0;
}