Cod sursa(job #2510190)

Utilizator chiravladChira Vlad chiravlad Data 15 decembrie 2019 22:47:04
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <fstream>
#include <queue>
const int NMAX = 101;
int A[NMAX+5][NMAX+5];
int B[NMAX+5][NMAX+5];

struct POINT
{
    int x,y;
};
std::queue<POINT> q;
//int dx[] = {-1,0,1,0};
//int dy[] = {0,1,0,-1};

int dx[] = {-1,-1, 0, 1, 1, 1,0,-1};
int dy[] = { 0, 1, 1, 1, 0, -1,-1,-1};
POINT startRomeo,startJulieta;

int m,n;

std::ifstream fin("rj.in");
std::ofstream fout("rj.out");

void afisareB()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
            fout<<B[i][j]<<" ";
        fout<<"\n";
    }
}

void afisareA()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
            fout<<A[i][j]<<" ";
        fout<<"\n";
    }
}

void leeA()
{
    int i;
    POINT fr,nou;
    q.push(startRomeo);
    A[startRomeo.x][startRomeo.y] = 1;
    while(!q.empty())
    {
        fr = q.front();
        q.pop();
        for(i=0; i<8; i++)
        {
            nou.x = fr.x + dx[i];
            nou.y = fr.y + dy[i];
            if(A[nou.x][nou.y]==0)
            {
                q.push(nou);
                A[nou.x][nou.y] = A[fr.x][fr.y] + 1;
            }
        }
    }
}

void leeB()
{
    while(!q.empty()) q.pop();
    int i;
    POINT fr,nou;
    q.push(startJulieta);
    B[startJulieta.x][startJulieta.y] = 1;
    while(!q.empty())
    {
        fr = q.front();
        q.pop();
        for(i=0; i<8; i++)
        {
            nou.x = fr.x + dx[i];
            nou.y = fr.y + dy[i];
            if(B[nou.x][nou.y]==0)
            {
                q.push(nou);
                B[nou.x][nou.y] = B[fr.x][fr.y] + 1;
            }
        }
    }
}


int main()
{
    int i,j;
    char ch;
    fin>>n>>m;
    fin.get(); //enter char
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            ch = fin.get();
            if(ch=='X') //obstacol
            {
                A[i][j] = -1;
                B[i][j] = -1;
            }
            if(ch=='R') //start Romeo
            {
                startRomeo.x= i;
                startRomeo.y = j;
            }
            if(ch=='J') //start Julieta
            {
                startJulieta.x = i;
                startJulieta.y = j;
            }
        }
        fin.get(); //enter char
    }

    //bordare
    for(j=0; j<=m+1; j++)
    {
        A[0][j] = A[n+1][j] = -1;
        B[0][j] = B[n+1][j] = -1;
    }
    for(i=0; i<=n+1; i++)
    {
        A[i][0] = A[i][m+1] = -1;
        B[i][0] = B[i][m+1] = -1;
    }
    leeA();
    leeB();
    int minim = 999999;
    POINT pozMin;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(A[i][j] == B[i][j]  && A[i][j]!=-1)
                if(A[i][j]<minim)
                {
                    minim = A[i][j];
                    pozMin.x = i;
                    pozMin.y = j;
                }
        }
    }
    fout<<minim<<" "<<pozMin.x<<" "<<pozMin.y;
    return 0;
}