Cod sursa(job #1096521)

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

const int NMAX = 100;

using namespace std;

ifstream input("rj.in");
ofstream output("rj.out");
int N , M;
char matrix[NMAX][NMAX];
int distante[NMAX][NMAX];
queue <pair<int,int>> coada;


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

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 ++;
    }

    for (int i = 0; i < N ; i++)
    {
        input.getline(matrix[i],NMAX);
        for (int j = 0; j < M ; j++)
        {
            distante[i][j] = -1;
            if (matrix[i][j] == 'R')
            {
                coada.push(make_pair(i,j));
                distante[i][j] = 0;
            }
            if (matrix[i][j] == 'J')
            {
                coada.push(make_pair(i,j));
                distante[i][j] = 0;
            }
        }
    }

    pair<int,int> newPoint , currentPoint , answerPoint = make_pair(NMAX,NMAX);
    int minDist = NMAX * NMAX;
    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 (matrix[newPoint.first][newPoint.second] == ' ')
                {
                    if(matrix[currentPoint.first][currentPoint.second] == 'R')
                    {
                        matrix[newPoint.first][newPoint.second] = 'R';
                        distante[newPoint.first][newPoint.second] = distante[currentPoint.first][currentPoint.second] + 1;
                        coada.push(newPoint);
                    }
                    else if (matrix[currentPoint.first][currentPoint.second] == 'J')
                    {
                        matrix[newPoint.first][newPoint.second] = 'J';
                        distante[newPoint.first][newPoint.second] = distante[currentPoint.first][currentPoint.second] + 1;
                        coada.push(newPoint);
                    }
                }
                else if ((matrix[newPoint.first][newPoint.second] == 'R' && matrix[currentPoint.first][currentPoint.second] == 'J') || (matrix[newPoint.first][newPoint.second] == 'J' && matrix[currentPoint.first][currentPoint.second] == 'R'))
                {
                    if (distante[newPoint.first][newPoint.second] > distante[currentPoint.first][currentPoint.second])
                    {
                        if (distante[newPoint.first][newPoint.second] < minDist)
                        {
                            minDist = distante[newPoint.first][newPoint.second];
                            answerPoint = newPoint;
                        }
                        else if (distante[newPoint.first][newPoint.second] == minDist)
                        {
                            if (answerPoint.first > newPoint.first) answerPoint = newPoint;
                            else if (answerPoint.first == newPoint.first && answerPoint.second > newPoint.second) answerPoint = newPoint;
                        }
                        matrix[newPoint.first][newPoint.second] = 'T';

                    }
                    else
                    {
                        if (distante[currentPoint.first][currentPoint.second] < minDist)
                        {
                            minDist = distante[currentPoint.first][currentPoint.second];
                            answerPoint = currentPoint;
                        }
                        else if (distante[currentPoint.first][currentPoint.second] == minDist)
                        {
                            if (answerPoint.first > currentPoint.first) answerPoint = currentPoint;
                            else if (answerPoint.first == currentPoint.first && answerPoint.second > currentPoint.second) answerPoint = currentPoint;
                        }
                        matrix[currentPoint.first][currentPoint.second] = 'T';
                    }
                }
            }
        }
    }

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



    return 0;
}