Cod sursa(job #2668570)

Utilizator BulaceanuAlexandraBulaceanu Alexandra-Irina BulaceanuAlexandra Data 5 noiembrie 2020 01:07:41
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

char citire[150];
int traseuR[110][110], traseuJ[110][110];
int lR, lJ, cR, cJ;
int tmin, intalnireL, intalnireC;
queue<int> romeoLin, romeoCol, julLin, julCol;
int n, m;

int dirL[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dirC[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

pair<int, int> coord[101];

bool nuIese(int x, int y, int n, int m)
{
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void LeeR()
{
    int l, c;
    while (!romeoLin.empty())
    {
        l = romeoLin.front();
        c = romeoCol.front();
        romeoLin.pop();
        romeoCol.pop();
        for (int i = 0; i <8; i++)
        {
            int li = l + dirL[i];
            int col = c + dirC[i];
            if (nuIese(li, col, n, m))
            {
                if (traseuR[li][col] == 0)
                {
                    traseuR[li][col] = traseuR[l][c] + 1;
                    if(traseuR[l][c] == -1)
                        traseuR[li][col]++;

                    romeoLin.push(li);
                    romeoCol.push(col);
                }
            }

        }
    }
}



void LeeJ()
{
    int l, c;
    while (!julLin.empty())
    {
        l = julLin.front();
        c = julCol.front();
        julLin.pop();
        julCol.pop();
        for (int i = 0; i < 8; i++)
        {
            int li = l + dirL[i];
            int col = c + dirC[i];
            if (nuIese(li, col, n, m))
            {
                if (traseuJ[li][col] == 0)
                {
                    traseuJ[li][col] = traseuJ[l][c] + 1;
                    if(traseuJ[l][c] == -1)
                        traseuJ[li][col]++;
                    julLin.push(li);
                    julCol.push(col);
                }
            }

        }
    }
}


int main()
{

    fin >> n >> m;
    fin.getline(citire, 150);

    for (int i = 1; i <= n; i++)
    {
        fin.getline(citire, 150);
        for (int j = 1; j <= m; j++)
        {
            char el = citire[j - 1];

            if (el == 'R')
            {
                lR = i;
                cR = j;
                traseuR[i][j] = -1;
                traseuJ[i][j] = -1;
            }
            if (el == 'J')
            {
                lJ = i;
                cJ = j;
                traseuR[i][j] = -1;
                traseuJ[i][j] = -1;
            }
            if (el == 'X')
            {
                traseuR[i][j] = -1;
                traseuJ[i][j] = -1;
            }
            if (el == ' ')
            {
                traseuR[i][j] = 0;
                traseuJ[i][j] = 0;
            }
        }
    }

    romeoLin.push(lR);
    romeoCol.push(cR);
    LeeR();

    julLin.push(lJ);
    julCol.push(cJ);
    LeeJ();



    tmin = INT_MAX;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            if (traseuR[i][j] == traseuJ[i][j] && traseuR[i][j] != -1 && traseuJ[i][j] != 0)
            {
                if (traseuJ[i][j] < tmin)
                {
                    tmin = traseuJ[i][j];
                    intalnireL = i;
                    intalnireC = j;
                }
            }
    }

    fout<<tmin + 1<<" "<<intalnireL<<" " <<intalnireC;

    return 0;
}