Cod sursa(job #1441613)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 24 mai 2015 11:35:13
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#include <vector>
#include <list>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int N,M;
int X1,Y1,X2,Y2;
const int INF = 0x3f3f3f3f;
bool Matrix[505][505];
list<int> Bucket[3];
bool Use[(1<<22)+5];
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
void Read()
{
    f>>N>>M>>X1>>Y1>>X2>>Y2;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            f>>Matrix[i][j];
}
inline bool Valid(int i,int j)
{
    return i>0 && j>0 && i<=N && j<=M && Matrix[i][j]==0;
}
void Change(int node,int neighb,int cost)
{
    if(cost>=3)
        cost-=3;
    if(Use[neighb]==0)
        {
        Bucket[cost].push_back(neighb);
        Use[neighb]=1;
        }
}
void buildEdge(int i,int j,int dir,int c,int b)
{
    int k=dir;
        if(c==0)
        {
            if(Valid(i+dx[k],j+dy[k])==1)
                Change((i << 9) + j + (k << 18),((i+dx[k]) << 9) + j + dy[k] + (k << 18),b);
            return;
        }
        int x=k+c;
        if(x>=8)
            x-=8;
        if(Valid(i+dx[x],j+dy[x])==1)
            Change((i << 9) + j + (dir << 18),((i+dx[x]) << 9) + j + dy[x] + (x << 18),b+c);
        x=k-c;
        if(x<0)
            x+=8;
        if(Valid(i+dx[x],j+dy[x])==1)
            Change((i << 9) + j + (dir << 18),((i+dx[x]) << 9) + j + dy[x] + (x << 18),b+c);
}

void Dijkstra()
{

    for(int k=0;k<8;k++)
        Bucket[0].push_back((X1 << 9) + Y1 + (k << 18)),Use[(X1 << 9) + Y1 + (k << 18)]=1;
    int p=0;
    for(int cost=0;cost<=N*M*2;cost++)
    {
        if(!Bucket[p].empty())
        {
            list<int> :: iterator it;
            for(int c=0;c<=2;c++)
            for(it=Bucket[p].begin();it!=Bucket[p].end();it++)
            {
                int node=*it;
                int x=node;
                int dir = x >> 18;
                int j = (x & 511);
                int i = (x >> 9) & 511;
                if(i==X2 && j==Y2)
                {
                    g<<cost<<"\n";
                    return;
                }
                buildEdge(i,j,dir,c,p);
            }
            Bucket[p].clear();
        }
        ++p;
        if(p==3)
            p=0;
    }
    g<<-1<<"\n";
}
int main()
{
    Read();
    Dijkstra();
    return 0;
}