Cod sursa(job #2508136)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 11 decembrie 2019 17:06:54
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
FILE *f,*g;
struct graph
{
    int node, next,cost;
}v[500002];
struct bla
{
    int x,y;
};
bla dir[10]={{0,0},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
struct queie
{
    int node, dir;
}coada[250002];
int a[502][502],start[250002],d[250002];
int n,m,xi,yi,xf,yf;
void read()
{
    fscanf(f,"%d %d %d %d %d %d",&m,&n,&xi,&yi,&xf,&yf);
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            fscanf(f,"%d",&a[i][j]);

    for(int i=0; i<=m+1; i++)
        a[i][0]=a[i][n+1]=1;
    for(int j=0; j<=n+1; j++)
        a[0][j]=a[m+1][j]=1;
}
void build_graph()
{   int k=0,z1,z2;
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(!a[i][j])
            {
                for(int l=1; l<=8; l++)
                {
                    if(!a[i+dir[l].x][j+dir[l].y])
                    {
                        z1=(i-1)*n+j;
                        z2=(i+dir[l].x-1)*n+j+dir[l].y;
                        v[++k].node=z2;
                        v[k].next=start[z1];
                        v[k].cost=l%4;
                        start[z1]=k;
                    }
                }
            }
        }
    }
}
void Bellmanford()
{
    int pi=0,ps=0,x,y,dist,dif;
    for(int i=1; i<=n*m; i++)
        d[i]=9999999;
    coada[pi].node=(xi-1)*n+yi;
    d[coada[pi].node]=0;
    while(ps<=pi)
    {
        x=coada[ps].node;
        y=coada[ps].dir;
        for(int i=start[x]; i; i=v[i].next)
        {   if(y-v[i].cost<0)
                dif=(y-v[i].cost)*(-1);
            else
                dif=y-v[i].cost;
            if(dif%4!=0 || y==0)
                dif%=4;
            dist=d[x]+dif;
            if(d[v[i].node]>dist)
            {
                d[v[i].node]=dist;
                coada[++pi].node=v[i].node;
                coada[pi].dir=v[i].cost;
            }
        }
        ps++;
    }
}
int main()
{
    f=fopen("car.in","r");
    g=fopen("car.out","w");
    read();
    build_graph();
    Bellmanford();
    fprintf(g,"%d",d[(xf-1)*n+yf]);
    fclose(f);
    fclose(g);
    return 0;
}