Cod sursa(job #2425461)

Utilizator diliriciraduDilirici Radu diliriciradu Data 24 mai 2019 20:31:05
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <fstream>
#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[n+5];
    fin.getline(aux, 2);
    for (int i = 0; i < n; i++){
        fin.getline(aux, m+5);
        for (int j = 0; j < m; j++)
            c[i][j] = aux[j];
    }
}

void traducere()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; 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 >= n || 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 < n; 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;
}