Cod sursa(job #2638164)

Utilizator popescustefanita09@yahoo.comPopescu Alberto Stefanita [email protected] Data 27 iulie 2020 13:04:25
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 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;
char v[nmax][nmax];
int d[nmax][nmax], d1[nmax][nmax], px, py;
void read()
{
    f >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f>>v[i][j];
}

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)
{
    q.push({xs, ys});
    d[xs][ys]=1;
    v[xs][ys]='X';
    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(v[cx][cy] == ' ')
                {
                    q.push({cx, cy});
                    d[cx][cy] = d[px][py] + 1;
                    v[cx][cy] = 'X';
                }
            }
        }
    }
}
void solve2(int xs, int ys)
{
    q1.push({xs, ys});
    d1[xs][ys]=1;
    v[xs][ys]='X';
    while(!q1.empty())
    {
        px = q1.front().first;
        py = q1.front().second;
        q1.pop();
        for(int i = 0; i < 8; ++i)
        {
            int cx = px + dx[i];
            int cy = py + dy[i];
            if(inside(cx, cy))
            {
                if(v[cx][cy] == ' ')
                {
                    q1.push({cx, cy});
                    d1[cx][cy] = d1[px][py] + 1;
                    v[cx][cy] = 'X';
                }
            }
        }
    }
}

int main()
{
    read();
    Min=9999;
    k=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(v[i][j]=='R')
            {
                k=k+1;
                solve(xs,ys);
                //memset(q,0,sizeof(q));
            }
            if(v[i][j]=='J')
            {
                solve2(xs,ys);
                k=k+1;
                //memset(q,0,sizeof(q));
            }
            if(k==2)
                break;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if((d[i][j]==d1[i][j]) && d[i][j]!=0)
               if(d[i][j]<Min)
                   Min=d[i][j];
    g<<Min;
    return 0;
}