Cod sursa(job #2425525)

Utilizator diliriciraduDilirici Radu diliriciradu Data 24 mai 2019 21:17:07
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <queue>

#define max 1000000
#define mp make_pair

using namespace std;

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

int n, m, ro[255][255], jul[255][255];
char c[255][255];
queue <pair<int,int>> Qr;
queue <pair<int,int>> Qj;

int coord1, coord2, mn = max, mnj = max;

int dirx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int diry[] = {1, -1, 0, 0, 1, -1, -1, 1};

void citire()
{
    fin>>n>>m;
    char aux[m+5];
    fin.getline(aux, 1);
    for (int i = 0; i < n; i++){
        fin.getline(aux, m + 1);
        for (int j = 0; j < strlen(aux); j++)
            c[i][j] = aux[j];
        for (int j = strlen(aux); j < m; j++)
            c[i][j] = ' ';
    }
}

/*
void afisare(int a[255][255])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            fout<<a[i][j]<<" ";
        fout<<"\n";
    }
}*/

void traducere()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (c[i][j] == ' ')
                ro[i][j] = jul[i][j] = max;
            if (c[i][j] == 'X')
                ro[i][j] = jul[i][j] = -2;
            if (c[i][j] == 'R')
            {
                ro[i][j] = 0;
                jul[i][j] = -2;
                Qr.push(mp(i, j));
            }
            if (c[i][j] == 'J')
            {
                jul[i][j] = 0;
                ro[i][j] = -2;
                Qj.push(mp(i, j));
            }
        }
}

void lee(int a[255][255], queue <pair<int,int>>& Q)
{
    while (!Q.empty())
    {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
        for (int i = 0; i < 8; i++)
        {
            int newx = x + dirx[i];
            int newy = y + diry[i];
            if (newx < 0 || newx >= m || newy < 0 || newy >= n || a[y][x] == -2 || a[newy][newx] == -2)
                continue;
            if (a[newy][newx] > a[y][x] + 1)
            {
                a[newy][newx] = a[y][x] + 1;
                Q.push(mp(newy, newx));
            }
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j] == max)
                a[i][j] = -1;
}

void raspuns()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (ro[i][j] == jul[i][j] && jul[i][j] > 0 && (jul[i][j] < mn))// || jul[i][j] == mn && j < mnj))
            {
                coord1 = i;
                coord2 = j;
                mn = jul[i][j];
                mnj = j;
            }
}

int main()
{
    citire();
    traducere();
    lee(ro, Qr);
    lee(jul, Qj);
    raspuns();
    fout<<mn + 1<<" "<<coord1 + 1<<" "<<coord2 + 1<<"\n";

    return 0;
}