Cod sursa(job #2152248)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 5 martie 2018 13:10:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
using namespace std;

const int N = 105;

pair<int,int> R, J;
int distR[N][N],distJ[N][N];
int n,m;

void bordeaza()
{
    int i;

    for(i=0;i<=n+1;i++)
        distR[i][0] = distR[i][m+1] = distJ[i][0] = distJ[i][m+1] = -1;
    for(i=0;i<=m+1;i++)
        distR[0][i] = distR[n+1][i] = distJ[0][i] = distJ[n+1][i] = -1;
}

void afisMat(int mat[N][N])
{
    for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=m+1;j++)
            cout<<mat[i][j]<<' ';
        cout<<'\n';
    }
    cout<<'\n';
}

void bf(int (&dist)[N][N], pair<int,int> start)
{
    queue< pair<int,int> > q;

    q.push(start);
    dist[start.first][start.second] = 1;

    int dirX[] = {-1,-1,-1, 0, 1, 1, 1, 0};
    int dirY[] = {-1, 0, 1, 1, 1, 0,-1, -1};
    int dir;

    pair<int,int> x;
    while(!q.empty())
    {
        x = q.front();
        q.pop();

        for(dir=0;dir<8;dir++)
        {
            int X = x.first + dirX[dir];
            int Y = x.second + dirY[dir];

            if(dist[X][Y] == 0)
            {
                q.push(make_pair(X,Y));
                dist[X][Y] = dist[x.first][x.second] + 1;
            }
        }
    }
}

int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");

    fin>>n>>m;
    int i,j;
    string line;
    getline(fin, line);

    for(i=1;i<=n;i++)
    {
        getline(fin, line);
        for(j=0;j<m;j++)
        {
            if(line[j] == 'R')
                R = make_pair(i, j+1);
            if(line[j] == 'J')
                J = make_pair(i, j+1);
            if(line[j] == 'X')
                distR[i][j+1] = distJ[i][j+1] = -1;
        }
    }

    bordeaza();

    bf(distJ,J);
    bf(distR,R);

    pair<int,int> p;
    int bst = 1000000;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(distJ[i][j] > 0 && distJ[i][j] == distR[i][j] && distJ[i][j] < bst)
            {
                bst = distJ[i][j];
                p = make_pair(i,j);
            }

    fout<<bst<<' '<<p.first<<' '<<p.second;


    fin.close();
    fout.close();
    return 0;
}