Cod sursa(job #3290367)

Utilizator popescubogdanPopescu Bogdan popescubogdan Data 30 martie 2025 15:37:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

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

int crx,cry,cjx,cjy;
int minn=20001;
int n,m;
int mij;
int mat[101][101];
char s[101][101];
bool frecv[101][101];
int dif[3]={0,1,-1},tip[3]={2,3,3},comb[3]={1,-1,0};

void lee()
{
    queue< pair<int,pair<int, int> > > Q;
    
    Q.push({1,{crx,cry}});
    mat[crx][cry]=1;
    
    while(Q.empty()!=1)
    {
        int xx=Q.front().second.first;
        int yy=Q.front().second.second;
        int pas=Q.front().first;
        
        if(pas>minn)
            return;
        if((xx==cjx && yy== cjy)&&((mat[xx][yy]-mat[crx][cry]-1)%2==0))
            if(pas<=minn)
                minn=pas;
                
        for(int i=0;i<3;i++)
            for(int j=0;j<tip[i];j++)
            {
                int pctx= xx+dif[i];
                int pcty= yy+comb[j];
                if((pctx>-1 && pctx<n) && (pcty>-1 && pcty<m))
                {
                    if(s[pctx][pcty]!='X')///daca pot sa trec pe aici
                    {
                        if(mat[pctx][pcty]==0 || mat[pctx][pcty]>=pas+1)
                        {
                            mat[pctx][pcty]=pas+1;
                            Q.push({pas+1,{pctx,pcty}});
                        }
                    }
                    else ///pe unde nu am voie sa trec
                        mat[pctx][pcty]=1001;
                }
                
            }
        Q.pop();
    }
}

int rasx=1001,rasy=1001;

void dfs(int xx,int yy)
{
    if(frecv[xx][yy])
        return;
    frecv[xx][yy]=1;
    
    if(mat[xx][yy]==mij)///e la jumatate
    {
        if(xx<rasx)
        {
            rasx=xx;
            rasy=yy;
        }
        else if(xx==rasx)
                if(yy<rasy)
                    rasy=yy;
        ///salvez
    }
        
    for(int i=0;i<3;i++)
        for(int j=0;j<tip[i];j++)
        {
            int pctx= xx+dif[i];
            int pcty= yy+comb[j];
            if((pctx>-1 && pctx<n) && (pcty>-1 && pcty<m))
            {
                if(mat[pctx][pcty]==mat[xx][yy]-1)
                    dfs(pctx,pcty);
            }
        }
    
}

int main()
{
    //int n,m;
    //char s[100][101];
    cin>>n>>m;
    cin.get();
    for(int i=0;i<n;i++)
    {
        cin.getline(s[i],m+1);
        int j=0;
        while(s[i][j]!='\0')
        {
            if(s[i][j]=='R')
                crx=i,cry=j;
            else if(s[i][j]=='J')
                cjx=i,cjy=j;
                
            j++;
        }
    }
    ///acum lee din R in J
    
    lee();
    
    mij=((mat[cjx][cjy]-mat[crx][cry])/2) + 1;
    
    dfs(cjx,cjy);
    
    /*
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<mat[i][j]<<" ";
        cout<<'\n';
    }*/
    cout<<mij<<" "<<rasx+1<<" "<<rasy+1;
    
    return 0;
}