Cod sursa(job #1158814)

Utilizator CostinVFMI CostinVictorGabriel CostinV Data 29 martie 2014 09:16:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 kb
#include<fstream>
#include<queue>

using namespace std;

int dx[]={0, 1, 0, -1, 1, 1, -1, -1};
int dy[]={1, 0, -1, 0, 1, -1, 1, -1};
int **harta, **harta1, n, m;
pair<int, int> Romeo, Julieta;
queue <pair<int,int> > q;

void BFS ()
{
    pair<int, int> curent, new_curent;
    q.push(Romeo);

    while(!q.empty())
    {
        curent = q.front();
        q.pop();

        for(int i=0; i<8; i++)
        {
            new_curent.first = curent.first + dx[i];
            new_curent.second = curent.second + dy[i];

            if (harta[new_curent.first][new_curent.second] ==0)
            {
                harta[new_curent.first][new_curent.second] = harta[curent.first][curent.second] + 1;
                q.push(new_curent);
            }
        }
    }

    q.push(Julieta);

    while(!q.empty())
    {
        curent = q.front();
        q.pop();

        for(int i=0; i<8; i++)
        {
            new_curent.first = curent.first + dx[i];
            new_curent.second = curent.second +dy[i];

            if(harta1[new_curent.first][new_curent.second] == 0)
            {
                harta1[new_curent.first][new_curent.second] = harta1[curent.first][curent.second] + 1;
                q.push(new_curent);
            }
        }
    }
}

int main()
{
    string linie;

    ifstream f("rj.in");
    f>>n>>m;

    harta = new int* [n+2];
    harta1= new int* [n+2];
    for(int i=0; i<=n+1; i++)
    {
        harta[i]= new int [m+2];
        harta1[i]=new int [m+2];
    }

    getline(f, linie);

    for(int i=1; i<=n; i++)
    {
        getline(f, linie);

        for(int j=0; j<=m; j++)
        {
            if(linie[j]==' ')
            {
                harta[i][j+1] = 0;
                harta1[i][j+1]= 0;
            }
            if(linie[j]=='X')
            {
                harta[i][j+1] = -1;
                harta1[i][j+1]= -1;
            }
            if(linie[j]=='R')
            {
                harta[i][j+1]=1;
                harta1[i][j+1]=0;
                Romeo.first=i;
                Romeo.second=j+1;
            }
            if(linie[j]=='J')
            {
                harta1[i][j+1]=1;
                harta[i][j+1]=0;
                Julieta.first=i;
                Julieta.second=j+1;
            }
        }
    }

    for(int i=0; i<=n+1; i++)
    {
        harta[i][0] = -1;
        harta[i][m+1] = -1;
        harta1[i][0] = -1;
        harta1[i][m+1] = -1;
    }

    for(int i=0; i<=m+1; i++)
    {
        harta[0][i] = -1;
        harta[n+1][i]=-1;
        harta1[0][i]=-1;
        harta1[n+1][i]=-1;
    }

    BFS();

    int minn = 0;
    pair <int, int> coord;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if (harta[i][j] == harta1[i][j] && harta[i][j]!=0 && harta[i][j]!=-1)
            {
                if(minn == 0)
                {
                    minn=harta[i][j];
                    coord = make_pair(i, j);
                }

                if(minn>harta[i][j])
                {
                    minn = harta[i][j];
                    coord = make_pair(i, j);
                }
            }
    ofstream g("rj.out");
    g<<minn<<" "<<coord.first<<" "<<coord.second;

    f.close();
    g.close();

    return 0;
}