Cod sursa(job #2425176)

Utilizator RaulG99Gioanca Raul RaulG99 Data 24 mai 2019 15:07:42
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

#define INF 99999
ifstream f("rj.in");
ofstream g("rj.out");

char c;
int  n, m,romeoMat[111][111],julieMat[111][111];
int minn,x,y;

int di[10] = {-1,-1,-1,0,1,1,1,0};
int dj[10] = {-1,0,1,1,1,0,-1,-1};

queue <pair <int,int> > C1,C2;


void citire()
{
    f >> n >> m;
    f.get();

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f.get(c);

            if(c == 'R')
            {
                C1.push(make_pair(i,j));
                romeoMat[i][j] = 1;
                julieMat[i][j] = 0;
            }
            else if(c == 'J')
            {
                C2.push(make_pair(i,j));
                julieMat[i][j] = 1;
                romeoMat[i][j] = 0;
            }
            else if(c == 'X')
            {
                romeoMat[i][j] = -1;
                julieMat[i][j] = -1;
            }
            else
            {
                romeoMat[i][j] = INF;
                julieMat[i][j] = INF;
            }
        }
        f.get();
    }
}

void bordare(int mat[111][111])
{
    for(int i = 1; i <= n; i++)
        mat[i][0] = mat[i][m+1] = -1;
    for(int j = 0; j <= m; j++)
        mat[0][j] = mat[n+1][j] = -1;
}

void rj(int mat[111][111], queue <pair<int,int> > C)
{
    pair <int,int> nodCurent;
    int x,y;
    while(C.empty()==false)
    {
        nodCurent=C.front();
        C.pop();
        x = nodCurent.first;
        y = nodCurent.second;
        for(int i = 0; i < 8; i++)
        {
            if(mat[x+di[i]][y+dj[i]] > 0 && mat[x+di[i]][y+dj[i]] > mat[x][y] + 1)
            {
                mat[x+di[i]][y+dj[i]] = mat[x][y] + 1;
                C.push(make_pair(x+di[i],y+dj[i]));
            }
        }
    }
}

int main()
{

    citire();
    bordare(romeoMat);
    bordare(julieMat);
    rj(romeoMat,C1);
    bordare(julieMat);
    rj(julieMat,C2);


    minn=INF;
    for(int i =1; i <=n; i++)
        for(int j = 1; j <= m; j++)
            if( romeoMat[i][j]>0 && romeoMat[i][j]==julieMat[i][j] && romeoMat[i][j]<minn)
            {
                minn=romeoMat[i][j];
                x=i;
                y=j;
            }
    g<<minn<<" "<<x<<" "<<y;

}