Cod sursa(job #217782)

Utilizator dragosmihaiDragos Oana dragosmihai Data 30 octombrie 2008 11:28:53
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <iostream>
#define maxx 320000;
#include <queue>
using namespace std;

int n,m,pi,pj,fi,fj;
int a[503][503],c[503][503],viz[503][503];//,dir[503][503];
int vi[8]={-1,-1,-1,0,1,1,1,0};
int vj[8]={-1,0,1,1,1,0,-1,-1};
queue<int> q;
queue<int> dir[503][503];

void init()
{
    for(int i=0;i<=n+1;i++)
    {
        a[i][0]=1;
        a[i][m+1]=1;
    }
    for(int i=0;i<=m+1;i++)
    {
        a[0][i]=1;
        a[n+1][i]=1;
    }
    c[pi][pj]=0;
}

void citire()
{
    ifstream f("car.in");
    f>>n>>m;
    f>>pi>>pj>>fi>>fj;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f>>a[i][j];
            c[i][j]=-1;
            if(a[i][j]==0)
                c[i][j]=maxx;
        }
    init();
}

int diferenta(int x,int y)
{
    if(x>y)
    {
     int aux=x;
     x=y;
     y=aux;
    }
    int cost=0;
    int z=1;
    for(int i=0;i<y-x;i++)
    {
        cost+=z;
        if(cost==4)
            z*=-1;
        if(cost==0)
            z*=-1;
    }
    return cost;
}

int dif(int i,queue<int> z)
{
    int pp=10;
    while(!z.empty())
    {
        int po=diferenta(i,z.front());
        if(pp>po)
            pp=po;
         z.pop();
    }
    return pp;
}

void autostrada()
{
    viz[pi][pj]=1;
    q.push(pi);
    q.push(pj);
    while(!q.empty())
    {
        int vfi=q.front();
        q.pop();
        int vfj=q.front();
        q.pop();
        for(int i=0;i<8;i++)
            if(a[vfi+vi[i]][vfj+vj[i]]==0)
            {
                if(!viz[vfi+vi[i]][vfj+vj[i]])
                {
                    viz[vfi+vi[i]][vfj+vj[i]]=1;
                    q.push(vfi+vi[i]);
                    q.push(vfj+vj[i]);
                }
                if(vfi==pi&&vfj==pj)
                    {
                        c[vfi+vi[i]][vfj+vj[i]]=0;
                        dir[vfi+vi[i]][vfj+vj[i]].push(i);
                    }
                else
                {
                    int cc=dif(i,dir[vfi][vfj]);
                    if(c[vfi+vi[i]][vfj+vj[i]]>=c[vfi][vfj]+cc)
                    {
                        dir[vfi+vi[i]][vfj+vj[i]].push(i);
                        c[vfi+vi[i]][vfj+vj[i]]=c[vfi][vfj]+cc;
                    }
                }
            }
    }
}

void fishi()
{
    cout<<"  ";
    for(int i=1;i<=m;i++)
        cout<<i<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<i<<" ";
        for(int j=1;j<=m;j++)
            cout<<c[i][j]<<" ";
        cout<<endl;
    }
}

int main()
{
    citire();
    autostrada();
   // fishi();
    ofstream g("car.out");
    g<<c[fi][fj]<<endl;
    g.close();
    return 0;
}