Cod sursa(job #2668267)

Utilizator RomanacheRoman Alexandru-George Romanache Data 4 noiembrie 2020 18:31:03
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>
#define N 123456789


using namespace std;

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

struct punct
{
    int x, y;
};

const int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dy[8] = {-1, 1, 0 ,0, -1, 1, -1, 1};

int n, m, x, y, minimum = N, distanta[2][101][101];
bool vizit[2][101][101];
string sir;
punct R, J;
queue <punct> coada;

void BFS(punct P, int tip)
{
    coada.push(P);
    distanta[tip][P.x][P.y] = 1;
    vizit[tip][P.x][P.y] = 1;
    while(!coada.empty())
    {
        punct p = coada.front();
        coada.pop();
        for(int k = 0; k < 8; k++)
        {
            int px = p.x + dx[k];
            int py = p.y + dy[k];
            if(!vizit[tip][px][py])
            {
                vizit[tip][px][py] = 1;
                distanta[tip][px][py] = distanta[tip][p.x][p.y] + 1;
                coada.push({px,py});
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    getline(fin, sir);
    for(int i = 1; i <= n; i++)
    {
        getline(fin, sir);
        for(int j = 0; j<min((int)sir.size(), m); j++)
        {
            vizit[0][i][j + 1] = vizit[1][i][j + 1] = (sir[j] == 'X');
            if(sir[j] == 'R')
            {
                R.x = i;
                R.y = j + 1;
            }
            if(sir[j] == 'J')
            {
                J.x = i;
                J.y = j + 1;
            }
        }
    }
    for(int i = 0; i <= n + 1; i++)
        vizit[0][i][0] = vizit[1][i][0] = vizit[0][i][m+1] = vizit[1][i][m+1] = 1;
    for(int j = 0; j <= m + 1; j++)
        vizit[0][0][j] = vizit[1][0][j] = vizit[0][n+1][j] = vizit[1][n+1][j] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <=m; j++)
            distanta[0][i][j] = distanta[1][i][j] = N;
    BFS(R,0);
    BFS(J,1);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(distanta[0][i][j] == distanta[1][i][j] && distanta[0][i][j] < minimum)
            {
                minimum = distanta[0][i][j];
                x = i;
                y = j;
            }
    fout << minimum << ' ' << x << ' ' << y;

    return 0;
}