Cod sursa(job #2668550)

Utilizator BulaceanuAlexandraBulaceanu Alexandra-Irina BulaceanuAlexandra Data 5 noiembrie 2020 00:17:06
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

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[l][c]++;

                    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[l][c]++;

                    julLin.push(li);
                    julCol.push(col);
                }
            }

        }
    }
}


int main()
{

    fin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
        {
            char el;
            if (el == 'R') {
                lR = i;
                cR = j;
                traseuR[i][j] = 0;
                traseuJ[i][j] = 0;
            }
            if (el == 'J') {
                lJ = i;
                cJ = j;
                traseuR[i][j] = 0;
                traseuJ[i][j] = 0;
            }
            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<<" "<<intalnireL<<" " <<intalnireC;

    return 0;
}