Cod sursa(job #3123020)

Utilizator Raul_AArdelean Raul Raul_A Data 21 aprilie 2023 18:00:42
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>
#define cin in
#define cout out
#define maxi 101
using namespace std;

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

int R[maxi][maxi],J[maxi][maxi],xr,yr,xj,yj,n,m,xf,yf,tmin=2e9;
char c[maxi];
bitset<maxi> a[maxi];
const int di[]={-1,-1,-1,0,0,1,1,1},dj[]={-1,0,1,-1,1,-1,0,1};

void read() 
{
    cin>>n>>m;
    cin.getline(c,1);
    for(int i=1;i<=n;i++)
    {
        cin.getline(c,m+1);
        for(int j=0;c[j];j++)
        {
            if(c[j]==' ')
                a[i][j+1]=0;
            else if(c[j]=='X')
                a[i][j+1]=1;
            else if(c[j]=='R')
                xr=i,yr=j+1;
            else if(c[j]=='J')
                xj=i,yj=j+1;
        }
    }
}

bool inside(int i,int j){
    return i>=1 and j>=1 and i<=n and j<=m;
} 

void RomeoLEE() 
{
    queue< pair<int,int> > Q;
    bitset<maxi> v[maxi];
    Q.push({xr,yr});
    v[xr][yr]=1;
    R[xr][yr]=0;
    int i,j;

    while(!Q.empty())
    {
        tie(i,j)=Q.front();
        Q.pop();
        
        for(int d=0;d<8;d++)
        {
            int ii=di[d]+i;
            int jj=dj[d]+j;
            
            if(inside(ii,jj) and a[ii][jj]==0 and v[ii][jj]==0)
            {
                R[ii][jj]=R[i][j]+1;
                v[ii][jj]=1;
                Q.push({ii,jj});
            }
        }
    }
}

void JulietaLEE() 
{
    queue< pair<int,int> > Q;
    bitset<maxi> v[maxi];
    Q.push({xj,yj});
    v[xj][yj]=1;
    J[xj][yj]=0;
    int i,j;

    while(!Q.empty())
    {
        tie(i,j)=Q.front();
        Q.pop();
        
        for(int d=0;d<8;d++)
        {
            int ii=di[d]+i;
            int jj=dj[d]+j;
            
            if(inside(ii,jj) and a[ii][jj]==0 and v[ii][jj]==0)
            {
                J[ii][jj]=J[i][j]+1;
                v[ii][jj]=1;
                Q.push({ii,jj});
            }
        }
    }
}

void solve() 
{
    RomeoLEE();
    JulietaLEE();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(R[i][j]==J[i][j] and tmin>R[i][j] and R[i][j]>0)
            {
                tmin=R[i][j];
                xf=i,yf=j;
            }
}

void print(){
    cout<<tmin+1<<' '<<xf<<' '<<yf;
}

int main()
{
    read();
    solve();
    print();
    return 0;
}