Cod sursa(job #1440770)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 23 mai 2015 14:08:14
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 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];
vector < list<int> > Bucket;
int D[505*505*8];
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(D[neighb]>D[node]+cost)
        {
        if(D[neighb]!=INF)
            Bucket[D[neighb]%3].remove(neighb);
        D[neighb]=D[node]+cost;
        Bucket[D[neighb]%3].push_back(neighb);
        }
}
void buildEdge(int i,int j,int dir)
{
    int c=0,k=dir;
    for(;c<=2;c++)
    {
        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),0);
            continue;
        }
        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),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),c);
    }
}
void buildG()
{
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            if(Matrix[i][j]==0)
            {
                for(int dir=0;dir<8;dir++)
                    buildEdge(i,j,dir);
            }
        }
}
void Dijkstra()
{
    for(int i=0;i<=500*500*8;i++)
        D[i]=INF;
    Bucket.resize(3);
    for(int k=0;k<8;k++)
        Bucket[0].push_back((X1 << 9) + Y1 + (k << 18)),D[(X1 << 9) + Y1 + (k << 18)]=0;
    int p=0;
    for(int cost=0;cost<=N*M*2;cost++)
    {
        if(!Bucket[p].empty())
        {
            list<int> :: iterator it;
            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<<D[node]<<"\n";
                    return;
                }
                buildEdge(i,j,dir);
            }
            Bucket[p].clear();
        }
        ++p;
        if(p==3)
            p=0;
    }
    g<<-1<<"\n";
}
int main()
{
    Read();
    Dijkstra();
    return 0;
}