Cod sursa(job #2509724)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 14 decembrie 2019 17:35:20
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
FILE *f,*g;
struct graph
{
    int node, next,cost;
}v[700002];
struct bla
{
    int x,y;
};
bla dir[15]={{0,0},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
struct queie
{
    int node, dir;
}coada[700002];
int a[602][602],start[500002],d[500002];
int how[10]={0,0,3,2,1,0,1,2,3};
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;
                        start[z1]=k;
                    }
                }
            }
        }
    }
}
void Bellmanford()
{
    int pi=0,ps=0,x,y,ind;
    for(int i=1; i<=n*m; i++)
        d[i]=9999999;
    coada[pi].node=(xi-1)*n+yi;
    coada[pi].dir=0;
    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)
        {
            ind=v[i].cost-y+1;
            if(ind<=0)
                ind+=8;
            if(y==0)
                ind=5;
            if(d[v[i].node]>d[x]+how[ind])
            {
                d[v[i].node]=d[x]+how[ind];
                coada[++pi].node=v[i].node;
                coada[pi].dir=v[i].cost+4;
                if(coada[pi].dir>8)
                    coada[pi].dir-=8;
            }
        }
        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;
}