Cod sursa(job #1096553)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 2 februarie 2014 12:19:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

const int NMAX = 102;

using namespace std;

ifstream input("rj.in");
ofstream output("rj.out");
int N , M;
char matrix[NMAX][NMAX];
int distanteR[NMAX][NMAX];
int distanteJ[NMAX][NMAX];

bool isInMatrix(const int & x , const int & y)
{
    return (x >= 0) && (x < N) && (y >= 0) && (y < M);
}

void BFS(pair<int,int> startPoint , int distante[NMAX][NMAX])
{

    for (int i = 0; i < N ; i++)
        for (int j = 0;j < M; j++)
            distante[i][j] = -1;

    distante[startPoint.first][startPoint.second] = 0;

    queue <pair<int,int>> coada;

    coada.push(startPoint);

    pair<int,int> newPoint , currentPoint;
    int dx[] = {-1,1,0,0,1,1,1,-1};
    int dy[] = {0,0,-1,1,1,-1,-1,-1};
    while (!coada.empty())
    {
        currentPoint = coada.front();
        coada.pop();
        for (int i = 0; i < 8 ; i++)
        {
            newPoint.first = currentPoint.first + dx[i];
            newPoint.second = currentPoint.second + dy[i];
            if (isInMatrix(newPoint.first,newPoint.second))
            {
                if (distante[newPoint.first][newPoint.second] == -1 && matrix[newPoint.first][newPoint.second] == ' ')
                {
                    distante[newPoint.first][newPoint.second] = distante[currentPoint.first][currentPoint.second] + 1;
                    coada.push(newPoint);
                }
            }
        }
    }
}

void printMatrix(int matrix[NMAX][NMAX])
{
     for (int i = 0; i < N ; i++)
     {
        cout << '\n';
        for (int j = 0; j < M ; j++)
         cout << matrix[i][j] << ' ';
     }
}

int main()
{

   char line[NMAX];
    input.getline(line,NMAX);

    N = 0 , M = 0;
    int poz = 0;

    while (line[poz] >= '0' && line[poz] <= '9')
    {
        N = N * 10 + (line[poz] - '0');
        poz ++;
    }
    poz++;

    while (line[poz] >= '0' && line[poz] <= '9')
    {
        M = M * 10 + (line[poz] - '0');
        poz ++;
    }
    int rx , ry , jx , jy;
    for (int i = 0; i < N ; i++)
    {
        input.getline(matrix[i],NMAX);
        for (int j = 0; j < M ; j++)
        {
            if (matrix[i][j] == 'R')
            {
                rx = i;
                ry = j;
            }
            if (matrix[i][j] == 'J')
            {
                jx = i;
                jy = j;
            }
        }
    }

    BFS(make_pair(rx,ry),distanteR);
    printMatrix(distanteR);
    BFS(make_pair(jx,jy),distanteJ);
    cout << '\n';
    printMatrix(distanteJ);
    pair<int,int> answerPoint = make_pair(NMAX,NMAX);
    int minDist = NMAX * NMAX;

    for (int i = 0; i < N ; i++)
        for (int j = 0; j < M ; j++)
    {
        if (distanteJ[i][j] == distanteR[i][j] && distanteJ[i][j] != -1)
        {
            if (minDist > distanteJ[i][j])
            {
                minDist = distanteJ[i][j];
                answerPoint = make_pair(i,j);
            }
            else if (minDist == distanteJ[i][j])
            {
                if (answerPoint.first > i)
                {
                    answerPoint.first = i;
                    answerPoint.second = j;
                }
                else if (answerPoint.first == i)
                {
                    answerPoint.second = min(answerPoint.second , j);
                }
            }
        }
    }


    output << minDist + 1 << ' ' << answerPoint.first + 1 << ' ' << answerPoint.second + 1;

    return 0;
}