Cod sursa(job #2006869)

Utilizator refugiatBoni Daniel Stefan refugiat Data 1 august 2017 08:07:55
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 505
using namespace std;
ifstream si("car.in");
ofstream so("car.out");
int x[MAXN][MAXN];
int d[(1<<21)+5];
vector<int>q[2];
int sol,n,m;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int xf,yf;
inline int cod(int i,int j,int dir)
{
    return ((i<<9)+j+(dir<<18));
}
void decod(int c,int&i,int&j,int&dir)
{
    j=c&511;
    i=(c>>9)&511;
    dir=c>>18;
}
bool expand(int st)
{
    int i,j,dir;
    int nst;
    decod(st,i,j,dir);
    nst=cod(i,j,(dir+7)%8);
    if(d[nst]>d[st]+1)
    {
        d[nst]=d[st]+1;
        q[d[nst]&1].push_back(nst);
    }
    nst=cod(i,j,(dir+1)%8);
    if(d[nst]>d[st]+1)
    {
        d[nst]=d[st]+1;
        q[d[nst]&1].push_back(nst);
    }
    i+=dx[dir];
    j+=dy[dir];
    if(i<1||j<1||i>n||j>m||x[i][j])
        return false;
    nst=cod(i,j,dir);
    if(d[nst]>d[st])
    {
        d[nst]=d[st];
        q[d[nst]&1].push_back(nst);
    }
    if(i==xf&&j==yf)
        return true;
    return false;
}
int main()
{
    si>>n>>m;
    int xs,ys;
    si>>xs>>ys>>xf>>yf;
    int st;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            si>>x[i][j];
    for(int i=0;i<(1<<21)+5;++i)
        d[i]=1<<30;
    for(int i=0;i<8;++i)
    {
        st=cod(xs,ys,i);
        q[0].push_back(st);
        d[st]=0;
    }
    while(q[0].size()+q[1].size())
    {
        while(!q[sol&1].empty())
        {
            st=q[sol&1].back();
            q[sol&1].pop_back();
            if(expand(st))
            {
                so<<sol<<'\n';
                return 0;
            }
        }
        ++sol;
    }
    so<<-1;
    return 0;
}