Cod sursa(job #1440620)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 23 mai 2015 13:30:45
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 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;
vector < pair<int,int> > G[505*505*8];
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 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)
                G[((i-1)*M+j)*8-8+dir].push_back(make_pair(((i+dx[k]-1)*M+j+dy[k])*8-8+k,0));
            continue;
        }
        int x=k+c;
        if(x>=8)
            x-=8;
        if(Valid(i+dx[x],j+dy[x])==1)
            G[((i-1)*M+j)*8-8+dir].push_back(make_pair(((i+dx[x]-1)*M+j+dy[x])*8-8+x,c));
        x=k-c;
        if(x<0)
            x+=8;
        if(Valid(i+dx[x],j+dy[x])==1)
            G[((i-1)*M+j)*8-8+dir].push_back(make_pair(((i+dx[x]-1)*M+j+dy[x])*8-8+x,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<=N*M*8;i++)
        D[i]=INF;
    Bucket.resize(500*500*2+1);
    for(int k=0;k<8;k++)
        Bucket[0].push_back(((X1-1)*M+Y1)*8+k-8),D[((X1-1)*M+Y1)*8+k-8]=0;
    for(int cost=0;cost<=N*M*2;cost++)
    {
        if(!Bucket[cost].empty())
        {
            list<int> :: iterator it;
            for(it=Bucket[cost].begin();it!=Bucket[cost].end();it++)
            {
                int node=*it;

                for(int i=0;i<G[node].size();i++)
                {
                    int neighb=G[node][i].first,cost=G[node][i].second;
                    if(D[neighb]>D[node]+cost)
                    {
                        if(D[neighb]!=INF)
                            Bucket[D[neighb]].remove(neighb);
                        D[neighb]=D[node]+cost;
                        Bucket[D[neighb]].push_back(neighb);
                    }
                }
            }
        }
    }
    int Min=INF;
    for(int i=0;i<8;i++)
        Min=min(Min,D[((X2-1)*M+Y2)*8+i-8]);
    if(Min==INF)
        Min=-1;
    g<<Min<<"\n";
}
int main()
{
    Read();
    buildG();
    Dijkstra();
    return 0;
}