Cod sursa(job #2276702)

Utilizator alexia208160Popescu Alexia Maria alexia208160 Data 5 noiembrie 2018 10:45:06
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <fstream>
#include <queue>

using namespace std;

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

int a[105][105],b[105][105];
int dx[]={-1, -1, -1, 0, 1, 1, 1, 0};
int dy[]={-1, 0, 1, 1, 1, 0, -1, -1};
char d[105];

int main()
{
    int n,m,x,y,xr, yr, xj, yj, t, tmin=101*101,xf,yf;
    fin>>n>>m;
    fin.get();
    for(x=0; x<n; x++)
    {
        fin.getline(d,105);
        for(y=0; y<m; y++)
        {

            if(d[y]=='X')
                a[x][y]=b[x][y]=-1;

            if(d[y]=='R')
            {
                xr = x;
                yr = y;
            }
            if(d[y]=='J')
            {
                xj = x;
                yj = y;
            }
            a[x][y]=b[x][y];
        }
    }
    struct casuta
    {
        int x,y;
    };
    queue<casuta> q;
    q.push({xr,yr});
    a[xr][yr]=1;
    while(!q.empty())
    {
        casuta p = q.front();
        for(int k=0; k<8; k++)
        {
            x = p.x + dx[k];
            y = p.y + dy[k];
            if(x>=0 && x<n && y>=0 && y<m)
            {
                if(a[x][y]==0)
                {
                    a[x][y]=a[p.x][p.y]+1;
                    q.push({x,y});
                }
            }
        }
        q.pop();
    }

    q.push({xj,yj});
    b[xj][yj]=1;
    while(!q.empty())
    {
        casuta p = q.front();
        for(int k=0; k<8; k++)
        {
            x = p.x + dx[k];
            y = p.y + dy[k];
            if(x>=0 && x<n && y>=0 && y<m)
            {
                if(b[x][y]==0)
                {
                    b[x][y]=b[p.x][p.y]+1;
                    q.push({x,y});
                    if(a[x][y]==b[x][y] && a[x][y]>0)
                    {
                       t=a[x][y];
                       if(t<tmin)
                       {
                           tmin = t;
                           xf=x;
                           yf=y;
                       }
                    }
                }
            }
        }
        q.pop();
    }

    fout<<a[xf][yf]<<" "<<xf+1<<" "<<yf+1<<" ";
    return 0;
}