Cod sursa(job #2894277)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 27 aprilie 2022 17:40:25
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
//Ilie Dumitru
#include<cstdio>
#include<queue>
typedef long long int ll;
const int NMAX=505;
const ll MOD=1000000007;

FILE* f=fopen("car.in", "r"), *g=fopen("car.out", "w");

int N, M, si, sj, ei, ej, minCost[NMAX][NMAX];
const int di[8]={1, 1, 1, 0, -1, -1, -1, 0};
const int dj[8]={1, 0, -1, -1, -1, 0, 1, 1};
char mat[NMAX][NMAX];
struct pos
{
    int i, j, dir;
};
std::queue<pos> q[3];

inline int abs(const int x) {return x-x*((x<0)<<1);}

int solve()
{
    int i, k, cost, change;
    pos curr, next;
    minCost[si][sj]=0;
    for(i=0;i<8;++i)
        q[0].push({si, sj, i});
    for(cost=0;!q[0].empty() || !q[1].empty() || !q[2].empty();++cost)
    {
        while(!q[cost%3].empty())
        {
            curr=q[cost%3].front();
            q[cost%3].pop();
            if(curr.i==ei && curr.j==ej)
                return cost;
            if(!mat[curr.i][curr.j])
            {
                mat[curr.i][curr.j]=1;
                for(k=0;k<8;++k)
                {
                    change=abs(di[curr.dir]-di[k])+abs(dj[curr.dir]-dj[k]);
                    if(change<3)
                    {
                        next.i=curr.i+di[k];
                        next.j=curr.j+dj[k];
                        next.dir=k;
                        if(next.i>-1 && next.i<N && next.j>-1 && next.j<M && !mat[next.i][next.j])
                            q[(cost+change)%3].push(next);
                    }
                }
            }
        }
    }
    return -1;
}

int main()
{
    int i, j, x;
    fscanf(f, "%d%d", &N, &M);
    fscanf(f, "%d%d%d%d", &si, &sj, &ei, &ej);
    --si;
    --sj;
    --ei;
    --ej;
    for(i=0;i<N;++i)
        for(j=0;j<M;++j)
            fscanf(f, "%d", &x), mat[i][j]=-x, minCost[i][j]=NMAX*NMAX;
    fprintf(g, "%d", solve());
    fclose(f);
    fclose(g);
    return 0;
}