Cod sursa(job #3207712)

Utilizator Raul_AArdelean Raul Raul_A Data 26 februarie 2024 19:44:59
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <cmath>
#include <fstream>
#include <stack>
#include <vector>
#include <cstring>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;

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

#define maxi 101

int R[maxi][maxi],J[maxi][maxi];
int xr,yr,xj,yj,n,m;
char c[maxi];
bitset<maxi> a[maxi];
int xf,yf,tmin=2e9;

const int di[]={-1,-1,-1,0,0,1,1,1};
const int 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 && j>=1 && i<=n && 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;
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        
        for(int d=0;d<8;d++)
        {
            int ii=di[d]+i;
            int jj=dj[d]+j;
            
            if(inside(ii,jj) && a[ii][jj]==0 && v[ii][jj]==0)
            {
                R[ii][jj]=R[i][j]+1;
                v[ii][jj]=1;
                Q.push({ii,jj});
            }
        }
        Q.pop();
    }
}

void JulietaLEE() 
{
    queue< pair<int,int> > Q;
    bitset<maxi> v[maxi];
    Q.push({xj,yj});
    v[xj][yj]=1;
    J[xj][yj]=0;
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        
        for(int d=0;d<8;d++)
        {
            int ii=di[d]+i;
            int jj=dj[d]+j;
            
            if(inside(ii,jj) && a[ii][jj]==0 && v[ii][jj]==0)
            {
                J[ii][jj]=J[i][j]+1;
                v[ii][jj]=1;
                Q.push({ii,jj});
            }
        }
        Q.pop();
    }
}




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] && tmin>R[i][j] && 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;
}