Cod sursa(job #3205093)

Utilizator Antonio_BiscoveanuAntonio Biscoveanu Antonio_Biscoveanu Data 18 februarie 2024 19:15:30
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
///aceasta este sursa pentru problema https://www.infoarena.ro/problema/rj
///punctaj:100
///grupa seniori

#include <bits/stdc++.h>
#define DIM 101

using namespace std;

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

int n,m,i,j,ir,jr,ij,jj;
char ch[DIM];
int tmin=INT_MAX,is,js;
bool a[DIM][DIM];
int dr[DIM][DIM];
int dj[DIM][DIM];
int dx[]={0, -1, -1, -1, 0, 1, 1, 1, 0};
int dy[]={0, -1, 0, 1, 1, 1, 0, -1, -1};
struct coada
{
    int lin;
    int col;
};
queue<coada>Q;
void bfs(int x, int y, int d[DIM][DIM])
{
    Q.push({x,y});
    d[x][y]=1;
    while(!Q.empty())
    {
        int l=Q.front().lin,c=Q.front().col;
        for(int i=1;i<=8;i++)
        {
            int lv=l+dx[i],cv=c+dy[i];
            if(lv>=1&&lv<=n&&cv>=1&&cv<=m)
                if(a[lv][cv]==0 && d[lv][cv]==0)
                {
                    Q.push({lv,cv});
                    d[lv][cv]=d[l][c]+1;
                }
        }
        Q.pop();
    }
}
int main()
{
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
    {
        fin.getline(ch,DIM);
        for(j=1;j<=m;j++)
        {
            if(ch[j-1]!=' ')
            {
                if(ch[j-1]=='X')
                    a[i][j]=1;
                if(ch[j-1]=='R')
                {
                    ir=i;
                    jr=j;
                }
                if(ch[j-1]=='J')
                {
                    ij=i;
                    jj=j;
                }
            }
        }
    }
    bfs(ir, jr, dr);
    bfs(ij, jj, dj);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            if(dr[i][j]!=0 && dr[i][j]==dj[i][j])
                if(dr[i][j]<tmin)
                {
                    tmin=dr[i][j];
                    is=i;
                    js=j;
                }
    }
    fout<<tmin<<" "<<is<<" "<<js;
    return 0;
}