Cod sursa(job #2954790)

Utilizator iLaurianLaurian Iacob iLaurian Data 15 decembrie 2022 12:27:21
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

void lee(int w);
bool inmat(int i, int j);

int a[105][105], b[105][105], c[105][105];
int n, m, ok, ij, jj, ir, jr, dint = 10500, xint, yint;

int main()
{
    int i, j;
    fin >> n >> m;
    fin.ignore();
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            char chr;
            ok = 0;
            fin.get(chr);
            if(chr == '\n')
            {
                ok = 1;
                break;
            }
            else
            {
                if(chr == 'X')
                {
                    a[i][j] = 1;
                }
                else if(chr == 'J')
                {
                    ij = i, jj = j;
                }
                else if(chr == 'R')
                {
                    ir = i, jr = j;
                }
            }
        }
        if(!ok)
        {
            fin.ignore();
        }
    }
    lee(0);
    lee(1);
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            if(b[i][j] == c[i][j] && b[i][j] != 0 && c[i][j] != 0)
            {
                if(b[i][j] < dint)
                {
                    dint = b[i][j];
                    xint = i;
                    yint = j;
                }
                else if(b[i][j] == dint)
                {
                    if(i < xint)
                    {
                        dint = b[i][j];
                        xint = i;
                        yint = j;
                    }
                    else if(i == xint)
                    {
                        if(j < yint)
                        {
                            dint = b[i][j];
                            xint = i;
                            yint = j;
                        }
                    }
                }
            }
        }
    }
    fout << dint << " " << xint << " " << yint;

    return 0;
}


void lee(int w)
{
    queue < pair < int, int > > q;
    int di[8] = {-1, 1, 0, 0, 1, 1, -1, -1}, dj[8] = {0, 0, -1, 1, 1, -1, -1, 1};
    if(w == 0)
    {
        b[ij][jj] = 1;
        q.push(make_pair(ij, jj));
    }
    else
    {
        c[ir][jr] = 1;
        q.push(make_pair(ir, jr));
    }
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int d = 0; d <= 7; d++)
        {
            int inou = x + di[d];
            int jnou = y + dj[d];
            if(inmat(inou, jnou) && a[inou][jnou] == 0)
            {
                if(w == 0 && b[inou][jnou] == 0)
                {
                    b[inou][jnou] = b[x][y] + 1;
                    q.push(make_pair(inou, jnou));
                }
                if(w == 1 && c[inou][jnou] == 0)
                {
                    c[inou][jnou] = c[x][y] + 1;
                    q.push(make_pair(inou, jnou));
                }
            }
        }
    }
}

bool inmat(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}