Cod sursa(job #2052585)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 30 octombrie 2017 19:52:13
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
//Californication
#include <bits/stdc++.h>
#define Nmax 505
#define directions 8
#define DIM 10000
using namespace std;
ofstream g("car.out");
int cursor=DIM-1;
char buffer[DIM];
void read(int &x)
{
    x=0;
    while(buffer[cursor]<'0' or buffer[cursor]>'9')
        if(++cursor==DIM)
        {
            cursor=0;
            fread(buffer,1,DIM,stdin);
        }
    while(buffer[cursor]>='0' and buffer[cursor]<='9')
    {
        x=x*10+buffer[cursor]-'0';
        if(++cursor==DIM)
        {
            cursor=0;
            fread(buffer,1,DIM,stdin);
        }
    }
}
int n,m,startx,starty,stopx,stopy;
struct tip
{
    int l,c,h;
};
deque <tip> dq;
int a[Nmax][Nmax];
int T[Nmax][Nmax][directions];
inline void validation(const int &x, const int &y, const int &nd, const int &od, const int &val, const int &b_f)
{
    if(!a[x][y] and T[x][y][nd]>val)
    {
        T[x][y][nd]=val;
        if(b_f) dq.push_back({x,y,nd});
        else dq.push_front({x,y,nd});
    }
}
const int dir[2]={7,1};
const int dx[directions]={-1,-1,-1,0,1,1,1,0};
const int dy[directions]={-1,0,1,1,1,0,-1,-1};
inline void Initialization()
{
    int i,j,k;
    for(i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=true;
    for(i=0;i<=m+1;i++)
        a[0][i]=a[n+1][i]=true;
    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++)
            for(k=0;k<directions;k++)
            T[i][j][k]=INT_MAX;
    for(i=0;i<directions;i++)
    {
        T[startx][starty][i]=0;
        dq.push_back({startx,starty,i});
    }
}
int main()
{
    freopen("car.in","r",stdin);
    read(n);
    read(m);
    read(startx);
    read(starty);
    read(stopx);
    read(stopy);
    int i,j,k,x,y,d,dirr;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            read(a[i][j]);
    Initialization();
    while(!dq.empty())
    {
        x=dq.front().l;
        y=dq.front().c;
        d=dq.front().h;
        dq.pop_front();
        if(x!=stopx or y!=stopy)
        {
            for(k=0;k<2;k++)
                validation(x,y,(d+dir[k])%directions,d,T[x][y][d]+1,true);
            validation(x+dx[d],y+dy[d],d,d,T[x][y][d],false);
        }
        else
        {
            g<<T[x][y][d];
            return 0;
        }
    }
    g<<-1;

    return 0;
}