Cod sursa(job #2764134)

Utilizator DavidAA007Apostol David DavidAA007 Data 19 iulie 2021 16:54:44
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<string.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[]={-1, 0, 1, 0},dj[]={ 0, 1, 0,-1};
int A[205][205], n , m,x,y,X1,Y1,X2,Y2;
int B[205][205];
void Lee1(int istart ,int jstart)
{
    queue<pair<int,int>> Q;
    Q.push(make_pair(istart , jstart));
    A[istart][jstart] = 1;
    while(! Q.empty())
    {
        int i = Q.front().first, j = Q.front().second;
        for(int k = 0 ; k < 4 ; k ++)
        {
            int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= n // element în matrice
                && A[iv][jv] == 0) // element liber si nemarcat
            {
                // marcam elementul vecin cu o valoare mai mare
                A[iv][jv] = A[i][j] + 1;
                // il adaugam in coada
                Q.push(make_pair(iv , jv));
            }
        }
        Q.pop(); // eliminam din coada
    }
}
void Lee2(int istart ,int jstart)
{
    queue<pair<int,int>> Q1;
    Q1.push(make_pair(istart , jstart));
    B[istart][jstart] = 1;
    while(! Q1.empty())
    {
        int i = Q1.front().first, j = Q1.front().second;
        for(int k = 0 ; k < 4 ; k ++)
        {
            int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= n // element în matrice
                && B[iv][jv] == 0) // element liber si nemarcat
            {
                // marcam elementul vecin cu o valoare mai mare
                B[iv][jv] = B[i][j] + 1;
                // il adaugam in coada
                Q1.push(make_pair(iv , jv));
            }
        }
        Q1.pop(); // eliminam din coada
    }
}
int main()
{
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;i++)
    {
        char ch[205];
        strcpy(ch,"");
        fin.getline(ch,205);
        for(int j=1;j<=m;j++)
        {
            //notam X cu -1
            if(ch[j-1]=='X')
            {
                A[i][j]=-1;
                B[i][j]=-1;
            }
            if(ch[j-1]=='R')
            {
                X1=i;
                Y1=j;
            }
            if(ch[j-1]=='J')
            {
                X2=i;
                Y2=j;
            }
        }
    }
    Lee1(X1,Y1);
    Lee2(X2,Y2);
    int minn=2000000000;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(A[i][j]==B[i][j] && A[i][j]!=-1 && A[i][j]!=0)
            {
                if(A[i][j]<minn)
                {
                    minn=A[i][j];
                }
            }
        }
    fout<<minn-1<<"\n";
    fin.close();
    fout.close();
    return 0;
}