Cod sursa(job #2868592)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 11 martie 2022 00:57:52
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
#pragma region Header
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
#include <map>
#include <thread>
#include <mutex>
#include <future>

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
#define endl '\n'
using namespace std;
#if 1

#include <fstream>

ifstream fin("rj.in");
ofstream fout("rj.out");
#define cin fin
#define cout fout
#endif

#pragma endregion
const int nmx = 1e2+3;
int a[nmx][nmx];
int n,m;
int resi,resj;
int tmin = INT_MAX;
int ri,rj;
int ji,jj;
struct Pct
{
    int i,j;
};
int d[nmx][nmx];
int& Depth(Pct p)
{
    return d[p.i][p.j];
}
int viz[nmx][nmx];
void Bfs()
{
    queue<Pct> q;
    q.push({ri,rj});
    q.push({ji,jj});
    viz[ri][rj] = viz[ji][jj] = 2;
    Pct off[] = {{0,1},{1,0},{-1,0},{0,-1}};
    while(q.empty() == false)
    {
        Pct frnt = q.front();
        q.pop();
        for (int i =0;i<4;i++)
        {
            Pct npz = {frnt.i + off[i].i,frnt.j + off[i].j};
            if( npz.i < 1 || npz.j < 1 || npz.i > n || npz.j > m || a[npz.i][npz.j] == 1)
                continue;
            if(viz[npz.i][npz.j] == 1)
            {
                if(Depth(frnt)+1 == Depth(npz))/// possible solution
                {
                    int t = Depth(npz);
                    if(t < tmin)
                    {
                        tmin = t;
                        resi = npz.i;
                        resj = npz.j;
                    }
                    else if (t == tmin)
                    {
                        if(npz.i < resi)
                        {
                            resi = npz.i;
                            resj = npz.j;
                        }
                        else if (npz.i == resi)
                        {
                            if(npz.j < resj)
                            {
                                resi = npz.i;
                                resj = npz.j;
                            }
                        }
                    }
                }
                continue;
            }
            else if (viz[npz.i][npz.j] == 2)
                continue;
            d[npz.i][npz.j] = Depth(frnt) + 1;
            viz[npz.i][npz.j] = 1;
            q.push(npz);
        }
    }
}
// conditie: linia punctului minima,
// apoi coloana minima
int main()
{
    cin >> n >> m;
    cin.ignore(200,'\n');
    for (int i=1;i<=n;i++)
    {
        char buf[nmx+1]{};
        cin.getline(buf,nmx);
        for(int j=1;j<=m;j++)
        {
            char x = buf[j-1];
            if(x == 'R')
            {
                ri = i;
                rj = j;
                continue;
            }
            else if (x == 'J')
            {
                ji = i;
                jj = j;
                continue;
            }

            a[i][j] = (x=='X' ? 1 : 0);
        }
    }
    Bfs();
    cout << tmin << " " << resi << " " << resj;
}