Cod sursa(job #2668591)

Utilizator iulia_caciucunescuIulia Caciucunescu iulia_caciucunescu Data 5 noiembrie 2020 02:12:23
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

queue <int> qx,qy;

int n,m,x1,y1,x2,y2,tmin=100000,bestx,besty;
int matr[101][101], matj[101][101];
int dx[8]= {-1,-1,-1,0,0,1,1,1}, dy[8]= {-1,0,1,-1,1,-1,0,1};

void afis(int mat[101][101])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<mat[i][j]<<" ";
        cout<<'\n';
    }
}

bool verif(int x,int y)
{
    if(x>0 && x<=n && y>0 && y<=m)
        return 1;
    else
        return 0;
}

void bfs(int mat[101][101],int x,int y)
{
    qx.push(x);
    qy.push(y);
    while(qx.empty()==0)
    {
        int nowx=qx.front();
        int nowy=qy.front();
        for(int i=0; i<8; i++)
        {
            int nextx=nowx+dx[i];
            int nexty=nowy+dy[i];
            if(verif(nextx,nexty)==1 && mat[nextx][nexty]==0)
            {
                mat[nextx][nexty]=mat[nowx][nowy]+1;
                qx.push(nextx);
                qy.push(nexty);
            }
        }
        qx.pop();
        qy.pop();
    }
}

void citire()
{
    in>>n>>m;
    in.get();
    for(int i=1; i<=n; i++)
    {
        char s[150];
        in.getline(s,150);
        for(int j=0; j<m; j++)
        {
            if(s[j]=='R')
            {
                x1=i;
                y1=j+1;
                matr[i][j+1]=1;
            }
            else if(s[j]=='J')
            {
                x2=i;
                y2=j+1;
                matj[i][j+1]=1;
            }
            else if(s[j]=='X')
            {
                matr[i][j+1]=matj[i][j+1]=-1;
            }
        }
    }
}

int main()
{
    citire();
    bfs(matr,x1,y1);
    bfs(matj,x2,y2);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(matr[i][j]==matj[i][j] && matr[i][j]<tmin && matj[i][j]>0)
            {
                tmin=matr[i][j];
                bestx=i;
                besty=j;
            }
        }
    }
    out<<tmin<<" "<<bestx<<" "<<besty;
    return 0;
}