Cod sursa(job #1155688)

Utilizator CostinVFMI CostinVictorGabriel CostinV Data 27 martie 2014 08:49:00
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<fstream>
#include<queue>
#define INF 9999999

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, n, m;
pair<int, int> Romeo, Julieta;
queue <pair<int,int> > q;

void BFS ()
{
    harta[Romeo.first][Romeo.second]=1;
    harta[Julieta.first][Julieta.second]=1;
    ofstream g("rj.out");

    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]>harta[curent.first][curent.second])
            {
                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(harta[new_curent.first][new_curent.second] == harta [curent.first][curent.second] + 1)
            {
                g<<harta[new_curent.first][new_curent.second]<<" "<<new_curent.first<<" "<<new_curent.second;
                return;
            }

            if(harta[new_curent.first][new_curent.second] > harta[curent.first][curent.second]
                && harta[new_curent.first][new_curent.second]!=INF)
                {
                    harta[new_curent.first][new_curent.second] = harta[curent.first][curent.second] + 1;
                    q.push(new_curent);
                }
        }
    }


}

int main()
{
    string linie;

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

    harta = new int* [m+2];
    for(int i=0; i<=n+1; i++)
        harta[i]=new int [n+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]=INF;
            if(linie[j]=='X')
                harta[i][j+1]=-1;
            if(linie[j]=='R')
            {
                harta[i][j+1]=1;
                Romeo.first=i;
                Romeo.second=j+1;
            }
            if(linie[j]=='J')
            {
                harta[i][j+1]=1;
                Julieta.first=i;
                Julieta.second=j+1;
            }
        }
    }

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

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

    BFS();

    return 0;
}