Cod sursa(job #2639595)

Utilizator popescustefanita09@yahoo.comPopescu Alberto Stefanita [email protected] Data 3 august 2020 00:54:19
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");
const int nmax = 2e2 + 3;
int n, k, x, y, xs, ys, xf, yf, Min, m, xr,  yr, xj, yj, solx, soly;
char s[nmax];
int d1[nmax][nmax], d2[nmax][nmax], a[nmax][nmax], px, py, b[nmax][nmax];
void read()
{
    f >> n >> m;
    f.get();
    for(int i = 1; i <= n; i++)
    {
        f.getline(s + 1,150);
        for(int j = 1; j <= m; j++)
        {
            if(s[j] == ' ')
            {
                a[i][j] = 0;
                b[i][j]=0;
            }
            else if(s[j] == 'R')
            {
                xr = i;
                yr = j;
            }
            else if(s[j] == 'J')
            {
                xj = i;
                yj = j;
            }
            else
            {
                a[i][j] = -1;
                b[i][j]=-1;
            }
        }
    }
}

queue < pair <int, int> > q,q1;

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

bool inside(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void solve(int xs, int ys, int d[nmax][nmax], int a[nmax][nmax])
{
    q.push({xs, ys});
    d[xs][ys]=1;
    a[xs][ys]=-2;
    while(!q.empty())
    {
        px = q.front().first;
        py = q.front().second;
        q.pop();
        for(int i = 0; i < 8; ++i)
        {
            int cx = px + dx[i];
            int cy = py + dy[i];
            if(inside(cx, cy))
            {
                if(a[cx][cy] == 0)
                {
                    q.push({cx, cy});
                    d[cx][cy] = d[px][py] + 1;
                    a[cx][cy] = -2;
                }
            }
        }
    }
}
int main()
{
    read();
    Min=9999999;
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;*/
    solve(xr,yr,d1,a);
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<d1[i][j]<<" ";
        cout<<endl;
    }*/

    solve(xj,yj,d2,b);
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<d2[i][j]<<" ";
        cout<<endl;
    }*/
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if((d1[i][j]==d2[i][j]) && d1[i][j]!=0)
               if(d1[i][j]<Min)
               {
                   Min=d1[i][j];
                   solx=i;
                   soly=j;
               }
    g<<Min<<" "<<solx<<" "<<soly;
    return 0;
}