Cod sursa(job #3183216)

Utilizator Ionut2212Nedelcu Alexandru Ionut Ionut2212 Data 11 decembrie 2023 10:50:56
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <iostream>
#include <queue>
#include <utility>
#include <fstream>

using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
int n, m, ij, jj, ir, jr, traseuj[101][101], traseur[101][101], st[] = {0, 1, -1, 0, 0, 1, -1, -1, 1}, dr[] = {0, 0, 0, 1, -1, 1, -1, 1, -1};
char ma[101][101];
void citire()
{
    fin >> n >> m;
    fin.get();
    for(int i = 1; i <= n; ++ i){
            fin.getline(ma[i],101);
         for(int j = 0; j < m; ++j)
        {
            char x;
            x = ma[i][j];
            if(x == ' ') traseur[i][j+1] = 0;
            else
            if(x == 'X') traseur[i][j+1] = -1;
            else
            if(x == 'R')
            {
                ir = i;
                jr = j+1;
                traseur[i][j+1] = 1;
            }
            else
            {
                ij = i;
                jj = j+1;
                traseuj[i][j+1] = 1;
                traseur[i][j+1] = 1;
            }
        }
    }

}
void afis()
{
    traseur[ij][jj] = 0;
    int minim = 999999, poz1, poz2;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++j)
            if(traseur[i][j] == traseuj[i][j] && traseuj[i][j] < minim && traseuj[i][j] != 0)
            {
                minim = traseuj[i][j];
                poz1 = i;
                poz2 = j;
            }
    }
    fout << minim << ' ' << poz1 << ' ' << poz2;
}
void lee(int istart, int jstart)
{
    queue<pair<int,int> > q;
    traseuj[istart][jstart] = 1;
    q.push(make_pair(istart,jstart));
    while(!q.empty())
    {
        int p1 = q.front().first,p2 = q.front().second;
        for(int j = 1; j <= 8; j++)
        {
            int iv = p1 + st[j], jv = p2 + dr[j];
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && traseur[iv][jv] == 0 && traseuj[iv][jv] == 0)
            {
                traseuj[iv][jv] = traseuj[p1][p2] + 1;
                q.push(make_pair(iv,jv));
            }
        }
        q.pop();
    }
}
void lee2(int istart, int jstart)
{
    queue<pair<int,int> > c;
    traseur[istart][jstart] = 1;
    c.push(make_pair(istart,jstart));
    while(!c.empty())
    {
        int p1 = c.front().first,p2 = c.front().second;
        for(int j = 1; j <= 8; j++)
        {
            int iv = p1 + st[j], jv = p2 + dr[j];
            //cout << iv << ' ' << jv << endl;
             if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && traseur[iv][jv] == 0)
            {

                traseur[iv][jv] = traseur[p1][p2] + 1;
                c.push(make_pair(iv,jv));
            }
        }
        c.pop();
    }
}
int main()
{
    citire();
    lee(ij,jj);
    lee2(ir,jr);
    afis();
    return 0;
}
/*
5 5
R XX
X X X
X XXX
X X X
X J X
*/