Cod sursa(job #2668513)

Utilizator anacomoAna-Maria Comorasu anacomo Data 4 noiembrie 2020 23:14:31
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>
using namespace std;

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

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

int n, m, matrix[101][101][2];
queue<pair<int, int>> coada;

bool valid(int x, int y, int rj)
{
    return (x >= 0 && y >= 0 && x < n && y < m && matrix[x][y][rj] == -1);
}

void BFS(int rj, int root_x, int root_y)
{
    matrix[root_x][root_y][rj] = 0;
    coada.push(make_pair(root_x, root_y));
    while (!coada.empty())
    {
        int curr_x = coada.front().first;
        int curr_y = coada.front().second;
        coada.pop();
        for (int i = 0; i < 8; i++)
        {
            int next_x = curr_x + dirx[i];
            int next_y = curr_y + diry[i];
            if (valid(next_x, next_y, rj))
            {
                matrix[next_x][next_y][rj] = matrix[curr_x][curr_y][rj] + 1;
                coada.push(make_pair(next_x, next_y));
            }
        }
    }
}

int main()
{
    int rx, ry, jx, jy;
    fin >> n >> m;
    fin.get();
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            char x;
            fin.get(x);
            if (x == 'X')
            {
                matrix[i][k][0] = -2;
                matrix[i][k][1] = -2;
            }
            else
            {
                matrix[i][k][0] = -1;
                matrix[i][k][1] = -1;
            }

            if (x == 'R')
            {
                rx = i;
                ry = k;
            }

            if (x == 'J')
            {
                jx = i;
                jy = k;
            }
        }
        fin.get();
    }

    BFS(0, rx, ry);
    BFS(1, jx, jy);

    int tmin = 10000;
    int rez_x, rez_y;
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            if (matrix[i][k][0] == matrix[i][k][1] && matrix[i][k][0] >= 0 && matrix[i][k][0] < tmin)
            {
                tmin = matrix[i][k][0];
                rez_x = i;
                rez_y = k;
            }
        }
    }

    fout << tmin + 1 << ' ' << rez_x + 1 << ' ' << rez_y + 1;
    return 0;
}