Cod sursa(job #2016168)

Utilizator victoreVictor Popa victore Data 28 august 2017 20:06:33
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<cstdio>
#include<vector>

using namespace std;

const int nmax=505;
const int inf=1e9;

vector<int>q[2];
int n,m,sx,sy,fx,fy,ax[]={-1,-1,0,1,1,1,0,-1},ay[]={0,1,1,1,0,-1,-1,-1};
int d[(1<<21)+7];
bool v[nmax][nmax];

inline int code(int x,int y,int dir)
{
    return (x<<9) + y + (dir<<18);
}

inline void decode(int nr,int &x,int &y,int &dir)
{
    y = nr&511;
    nr>>=9;
    x =  nr&511;
    nr>>=9;
    dir=nr;
}

inline bool isnot(int x,int y)
{
    return (x < 1 || y < 1 || x>n || y>m || v[x][y]);
}

inline bool rezolva(int stare)
{
    int x,y,dir,cstare;
    decode(stare,x,y,dir);
    cstare = code(x,y,((dir+7)&7));
    if(d[cstare] > d[stare] + 1)
    {
        d[cstare] = d[stare] + 1;
        q[d[cstare]&1].push_back(cstare);
    }
    cstare = code(x,y,((dir+1)&7));
    if(d[cstare] > d[stare] + 1)
    {
        d[cstare] = d[stare] + 1;
        q[d[cstare]&1].push_back(cstare);
    }
    x+=ax[dir];
    y+=ay[dir];
    if(isnot(x,y))
        return 0;
    cstare = code(x,y,dir);
    if(d[cstare] > d[stare])
    {
        d[cstare] = d[stare];
        q[d[cstare]&1].push_back(cstare);
    }
    return (x == fx && y == fy);
}

int main()
{
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    int i,j;
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&v[i][j]);
    for(i=0;i< (1<<21)+5; ++i)
        d[i]=inf;
    int stare;
    for(i=0;i<8;++i)
    {
        stare=code(sx,sy,i);
        q[0].push_back(stare);
        d[stare]=0;
    }
    int ind=0;
    while(q[0].size() || q[1].size())
    {
        while(q[ind&1].size())
        {
            stare=q[ind&1][q[ind&1].size()-1];
            q[ind&1].pop_back();
            if(rezolva(stare))
            {
                printf("%d",ind);
                return 0;
            }
        }
        ++ind;
    }
}