Cod sursa(job #2764149)

Utilizator DavidAA007Apostol David DavidAA007 Data 19 iulie 2021 17:20:00
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<string.h>
#include<iomanip>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

int di[8]={-1,-1,-1,0,1,1,1,0};
int dj[8]={-1,0,1,1,1,0,-1,-1};
int A[205][205], n , m,x,y,X1,Y1,X2,Y2,pozi,pozj;
int B[205][205];
char ch[105];
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 < 8 ; k ++)
        {
            int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m // 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 < 8 ; k ++)
        {
            int iv = i + di[k], jv = j + dj[k]; // coordonatele vecinului
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m // 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();
    fin.get();
    for(int i=1;i<=n;i++)
    {
        strcpy(ch,"");
        fin.getline(ch,105);
        //cout<<ch<<"***\n";
        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);
    //debugging=hell
    /*
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<setw(3)<<A[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n\n";
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<setw(3)<<B[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n\n";
     */
    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];
                    pozi=i;
                    pozj=j;
                }
            }
        }
    fout<<minn<<" "<<pozi<<" "<<pozj;
    fin.close();
    fout.close();
    return 0;
}