Cod sursa(job #2413397)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 23 aprilie 2019 13:09:31
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <deque>
#include <cstring>
#define DIM 510
#define INF 2000000000
using namespace std;

ifstream fin ("car.in");
ofstream fout ("car.out");
int n,m,i,j,ic,jc,iv,jv,dir,D,mini,istart,jstart,ifin,jfin,new_dir;
deque < pair<pair<int,int>,int> > c;
int a[DIM][DIM],f[DIM][DIM][10],d[DIM][DIM][10];
int di[] = {0,-1,-1,0,1,1,1,0,-1};
int dj[] = {0,0,1,1,1,0,-1,-1,-1};

inline bool inmat (int i, int j){
    if (i >= 1 && i <= n && j >= 1 && j <= m)
        return 1;
    return 0;
}
int main (){

    fin>>n>>m>>istart>>jstart>>ifin>>jfin;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            fin>>a[i][j];

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

    for (dir=1;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;
            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 = 8;

        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 >= 9)
            new_dir = 1;

        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;

    return 0;
}