Cod sursa(job #957252)

Utilizator giminis96Pavel Stefan Cristian giminis96 Data 4 iunie 2013 18:16:37
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.35 kb
//problema rj infoarena

#include <iostream>
#include <fstream>
#define dim 100
#define inf -1

using namespace std;

struct pozitie
{
    int x,y;
}R,J,w;

struct nod
{
    int x,y;
    nod *leg;
}*p,*u;

int oras2[dim][dim],n,m;
int  romeo[dim][dim],julieta[dim][dim];
char oras[dim][dim];

void citeste()
{
    ifstream in("rj.in");
    in>>n>>m;
    int i;
    in.get();
    for(i=0;i<n;i++)
        in.getline(oras[i],100);
    in.close();
}

void afis(int x[dim][dim])
{
    int i,j;
    for(i = 0 ; i < n ; i++)
     {
        for(j = 0 ; j < m ;j++)
            cout<<x[i][j]<<" ";
        cout<<endl;
     }
}

void decodare()
{
    int i,j;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        {
            if(oras[i][j] == 'R')
                {
                    R.x = i;
                    R.y = j;
                }
            if(oras[i][j] == 'J')
                {
                    J.x = i;
                    J.y = j;
                }
            if(oras[i][j] == 'X')
                oras2[i][j] = 1;
            else
                oras2[i][j] = 0;
        }
}

void sterge_coada()
{
    nod *aux = new nod;
    while(p != NULL)
    {
        aux = p->leg;
        delete p;
        p = aux;
    }

}

void adauga_nod(int x_nou,int y_nou)
{
    nod *aux = new nod;
    aux -> x = x_nou;
    aux -> y = y_nou;
    aux -> leg = NULL;
    if(p == NULL)
    {
        p = new nod;
        u = new nod;
        p = aux;
        u = aux;
    }
    else
    {
        u -> leg = aux;
        u = aux;
    }
}

bool conditii(int x_nou,int y_nou,int marcaj[dim][dim],int pas)
{
    if(x_nou < 0 || x_nou > n-1)
        return 0;
    if(y_nou < 0 || y_nou > m-1)
        return 0;
    if(marcaj[x_nou][y_nou] == inf || marcaj[x_nou][y_nou] > pas)
        return 1;
    return 0;
}

void initializare(int x[dim][dim])
{
    int i,j;
    for(i = 0 ; i < n ; i++)
        for(j = 0 ; j < m ; j++)
            {
                if(oras2[i][j] == 0)
                    x[i][j] = inf;
                else
                    x[i][j] = -2;

            }
}

void lee(int marcaj[dim][dim])
{
    nod *curent = new nod;
    curent = p;
    int pas = 1;
    initializare(marcaj);
    romeo[R.x][R.y] = 0;
    julieta[R.x][R.y] = 0;
    julieta[J.x][J.y] = 0;
    romeo[J.x][J.y] = 0;
    while(curent != NULL)
    {
        //nord
        if(conditii(curent -> x-1 , curent -> y , marcaj , pas) == 1)
        {
            adauga_nod(curent -> x-1 , curent ->y);
            marcaj[curent -> x-1][curent -> y] = marcaj[curent -> x][curent -> y] + 1;
            //cout<<"n  ";
        }

        //sud
        if(conditii(curent -> x+1 , curent -> y , marcaj , pas) == 1)
        {
            adauga_nod(curent -> x+1 , curent ->y);
            marcaj[curent -> x+1][curent -> y] = marcaj[curent -> x][curent -> y] + 1;
            //cout<<"s  ";
        }

        //est
        if(conditii(curent -> x , curent -> y+1 , marcaj , pas) == 1)
        {
            adauga_nod(curent -> x , curent ->y+1);
            marcaj[curent -> x][curent -> y+1] = marcaj[curent -> x][curent -> y] + 1;
            //cout<<"e  ";
        }

        //vest
        if(conditii(curent -> x , curent -> y-1 , marcaj , pas) == 1)
        {
            adauga_nod(curent -> x , curent ->y-1);
            marcaj[curent -> x][curent -> y-1] = marcaj[curent -> x][curent -> y] + 1;
            //cout<<"v  ";
        }
        pas++;
        curent = curent -> leg;
    }
}

int modul(int a)
{
    if(a<0)
        return -a;
    return a;
}

void distanta_minima()
{
    int i,j;
    bool ok = 1;
    int pasi1;
    int minim = 8737643,coloana,minim2, dif;
    for(i=R.x;i<n;i++)
        for(j=R.y;j<m;j++)
        {
            if(romeo[i][j] > 0  && julieta[i][j] > 0)
                {
                    dif = modul(romeo[i][j] - julieta[i][j]);
                    if(dif < minim)
                        {
                            minim = dif;
                            w.x = i;
                            w.y = j;
                        }
                }
            /*
            if(romeo[i][j] == inf)
                continue;
            if(romeo[i][j] == -2)
                continue;
            if(romeo[i][j] == 0 || julieta[i][j] == 0)
                continue;
            if(ok == 1 && romeo[i][j] != 0)
            {
                minim = romeo[i][j] + julieta[i][j];
                coloana = j;
                w.x = i;
                w.y = j;
                pasi1 = minim/2;
                minim2 = modul(romeo[i][j] - julieta[i][j]);

                ok = 0;
            }

            if(ok == 0)
            {
                if(romeo[i][j] + julieta[i][j] < minim && modul(romeo[i][j] - julieta[i][j]) < minim2)
                    {
                        minim = romeo[i][j] + julieta[i][j];
                        coloana = j;
                        w.x = i;
                        w.y = j;
                        pasi1 = minim/2;
                    }
                if(romeo[i][j] + julieta[i][j] == minim )
                    if( j < coloana || modul(romeo[i][j] - julieta[i][j]) < minim2)
                    {
                        minim = romeo[i][j] + julieta[i][j];
                        coloana = j;
                        w.x = i;
                        w.y = j;
                        pasi1 = minim/2;
                    }
            }
            cout << "minim2 = " << minim2 << endl;
            cout<<"pozitia "<<i<<" "<<j<<" minim="<<minim<<endl;
            */
        }
    //cout << "Valoarea minima a diferentei se obtine pentru : " << minim << endl;
    //cout << w.x << " , " << w.y << endl;
    ofstream out("rj.out");
    out<<(romeo[w.x][w.y] + julieta[w.x][w.y])/2<<' '<<w.x+1<<' '<<w.y+1;
    out.close();
}

int main()
{
    citeste();
    decodare();
    romeo[R.x][R.y] = 0;
    julieta[R.x][R.y] = 0;
    julieta[J.x][J.y] = 0;
    romeo[J.x][J.y] = 0;
    p = NULL;
    u = NULL;
    adauga_nod(R . x , R . y);
    lee(romeo);
    //afis(romeo);
    //cout<<endl;
    //cout<<endl;
    sterge_coada();
    p = NULL;
    u = NULL;
    adauga_nod(J . x , J . y);
    lee(julieta);
    //afis(julieta);
    distanta_minima();
    return 0;
}