Cod sursa(job #2030047)

Utilizator LucianTLucian Trepteanu LucianT Data 30 septembrie 2017 23:17:24
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>
using namespace std;
const int maxN=505;
const int INF=0x3f3f3f3f;

class inParser
{
public:
    inParser(){};

    inParser(const char *file_name)
    {
        input_file=fopen(file_name,"r");
        cursor=0;
        fread(buffer,SIZE,1,input_file);
    }

    inline inParser &operator >>(int &n)
    {
        while(buffer[cursor]<'0' || buffer[cursor]>'9')
            advance();

        n=0;
        while('0'<=buffer[cursor] && buffer[cursor]<='9'){
            n=n*10+buffer[cursor]-'0';
            advance();
        }

        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE=1<<15;
    int cursor;
    char buffer[SIZE];

    inline void advance()
    {
        cursor++;
        if(cursor==SIZE){
            cursor=0;
            fread(buffer,SIZE,1,input_file);
        }
    }
};

const int dx[]={-1,-1,-1,0,1,1,1,0};
const int dy[]={-1,0,1,1,1,0,-1,-1};

int a[maxN][maxN];
int dist[maxN][maxN][8];
int n,m,xst,yst,xfn,yfn;
deque<pair<pair<int,int>,int> >deq;

int main()
{
    inParser f("car.in");
    freopen("car.out","w",stdout);

    f>>n>>m;
    f>>xst>>yst>>xfn>>yfn;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f>>a[i][j];

    memset(dist,INF,sizeof(dist));

    for(int i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=1;

    for(int i=0;i<=m+1;i++)
        a[0][i]=a[n+1][i]=1;

    for(int i=0;i<8;i++){
        dist[xst][yst][i]=0;
        deq.push_front({{xst,yst},i});
    }

    while(!deq.empty())
    {
        int x=deq.front().first.first;
        int y=deq.front().first.second;
        int dir=deq.front().second;
        deq.pop_front();

        if(x==xfn && y==yfn){
            printf("%d",dist[x][y][dir]);
            return 0;
        }

        int newdir=(dir+7)%8;
        if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
            dist[x][y][newdir]=dist[x][y][dir]+1;
            deq.push_back({{x,y},newdir});
        }

        newdir=(dir+1)%8;
        if(!a[x][y] && dist[x][y][newdir]>dist[x][y][dir]+1){
            dist[x][y][newdir]=dist[x][y][dir]+1;
            deq.push_back({{x,y},newdir});
        }

        newdir=dir;
        if(!a[x+dx[dir]][y+dy[dir]] && dist[x+dx[dir]][y+dy[dir]][newdir]>dist[x][y][dir]){
            dist[x+dx[dir]][y+dy[dir]][newdir]=dist[x][y][dir];
            deq.push_front({{x+dx[dir],y+dy[dir]},newdir});
        }
    }

    printf("-1");

    return 0;
}