Cod sursa(job #2588392)

Utilizator As932Stanciu Andreea As932 Data 24 martie 2020 19:05:18
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

const int nmax=105;
const int mmax=105;

int dx[8]={-1,-1,1,1,-1,0,1,0};
int dy[8]={-1,1,1,-1,0,1,0,-1};

int n,m,a[nmax][mmax],mnR[nmax][mmax],mnJ[nmax][mmax];
int ir,jr,ij,jj;
struct cell
{
    int x,y;
};

void read_data()
{
    char b[mmax];

    fin>>n>>m;
    fin.get();

    for(int i=1;i<=n;i++)
    {
        fin.getline(b,m+2);
        for(int j=0;j<m;j++)
            if(b[j]=='R')
            {
                a[i][j+1]=-2;
                ir=i,jr=j+1;
            }
            else if(b[j]=='J')
            {
                a[i][j+1]=-2;
                ij=i,jj=j+1;
            }
            else if(b[j]=='X')
                a[i][j+1]=-1;
    }
}

bool okei(int lin,int col)
{
    if(lin>=1 && lin<=n && col>=1 && col<=m)
        return true;
    return false;
}

void bfs_algR()
{
    deque <cell> d;
    d.push_back({ir,jr});
    mnR[ir][jr]=1;

    while(!d.empty())
    {
        int lin=d.front().x;
        int col=d.front().y;
        d.pop_front();

        for(int k=0;k<8;k++)
        {
            int ll=lin+dx[k];
            int cc=col+dy[k];

            if(okei(ll,cc) && (a[ll][cc]==0))
                if(mnR[ll][cc]==0)
                {
                    mnR[ll][cc]=mnR[lin][col]+1;
                    d.push_back({ll,cc});
                }
        }
    }
}

void bfs_algJ()
{
    deque <cell> d;
    d.push_back({ij,jj});
    mnJ[ij][jj]=1;

    while(!d.empty())
    {
        int lin=d.front().x;
        int col=d.front().y;
        d.pop_front();

        for(int k=0;k<8;k++)
        {
            int ll=lin+dx[k];
            int cc=col+dy[k];

            if(okei(ll,cc) && (a[ll][cc]==0))
                if(mnJ[ll][cc]==0)
                {
                    mnJ[ll][cc]=mnJ[lin][col]+1;
                    d.push_back({ll,cc});
                }
        }
    }
}

void solve()
{
    bfs_algR();
    bfs_algJ();

    int tmin=nmax*mmax,x,y;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mnR[i][j]==mnJ[i][j] && mnR[i][j]<tmin && mnR[i][j]>0)
            {
                tmin=mnR[i][j];
                x=i;
                y=j;
            }
    fout<<tmin<<" "<<x<<" "<<y;
}

int main()
{
    read_data();
    solve();

    return 0;
}