Cod sursa(job #217851)

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

struct cost_dir
{
    vector<int> dir;
    vector<int> ct;
};

cost_dir c[200][200];

int n,m,pi,pj,fi,fj;
int a[502][502],viz[500][500];
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;

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-1][pj-1].ct.push_back(0);
    c[pi-1][pj-1].dir.push_back(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;
}
/*
void pushc(int vfi,int vfj,int i,int c)
{
    c[vfi][vfj].dir.push_back(i);
    c[vfi][vfj].ct.push_back(c);
}
*/
void autostrada()
{
    viz[pi-1][pj-1]=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]-1][vfj+vj[i]-1])
                {
                    viz[vfi+vi[i]-1][vfj+vj[i]-1]=1;
                    q.push(vfi+vi[i]);
                    q.push(vfj+vj[i]);
                }
                if(vfi==pi&&vfj==pj)
                    {
                        //pushc(vfi+vi[i],vfj+vj[i],i,0);
                            c[vfi+vi[i]-1][vfj+vj[i]-1].dir.push_back(i);
                            c[vfi+vi[i]-1][vfj+vj[i]-1].ct.push_back(0);
                    }
                else
                {
                    int l=c[vfi-1][vfj-1].dir.size();
                   for(int v=0;v<l;v++)
                   {
                        int cc=diferenta(i,c[vfi-1][vfj-1].dir[v]);
                        c[vfi+vi[i]-1][vfj+vj[i]-1].dir.push_back(i);
                        c[vfi+vi[i]-1][vfj+vj[i]-1].ct.push_back(cc+c[vfi-1][vfj-1].ct[v]);
                    }
                }
            }
    }
}

int mini(int x,int y)
{
    int mi=maxx;
    for(int i=0;i<c[x][y].ct.size();i++)
        if(mi>c[x][y].ct[i]&&mi!=0)
            mi=c[x][y].ct[i];
    return mi;
}

int main()
{
    citire();
    autostrada();
    ofstream g("car.out");
    g<<mini(fi-1,fj-1)<<endl;
    g.close();
    return 0;
}