Cod sursa(job #3129203)

Utilizator David2007David Preda David2007 Data 13 mai 2023 12:49:16
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m,i,j,x1,x2,y3,y2,a,b,x,y,di,dj,min1,rx,ry,jx,jy;
char v[200];
int o[200][200];
int w[200][200],w1[200][200];

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

struct coordonate
{
    int x,y;
};

coordonate h1,h2;

queue <coordonate> q;

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

void LeeR()
{
    h1.x=rx;
    h1.y=ry;
    w[h1.x][h1.y]=1;
    q.push(h1);
    while(!q.empty())
    {
        h1=q.front();
        q.pop();
        for(i=0;i<8;i++)
        {
            h2.x=dx[i]+h1.x;
            h2.y=dy[i]+h1.y;
            if(interior(h2.x,h2.y)&&(w[h1.x][h1.y]+1<w[h2.x][h2.y]||w[h2.x][h2.y]==0)&&o[h2.x][h2.y]!=1)
            {
             w[h2.x][h2.y]=w[h1.x][h1.y]+1;
             q.push(h2);
            }
        }
    }

}

void LeeJ()
{
    h1.x=jx;
    h1.y=jy;
    w1[h1.x][h1.y]=1;
    q.push(h1);
    while(!q.empty())
    {
        h1=q.front();
        q.pop();
        for(i=0;i<8;i++)
        {
            h2.x=h1.x+dx[i];
            h2.y=h1.y+dy[i];
            if(interior(h2.x,h2.y)&&(w1[h1.x][h1.y]+1<w1[h2.x][h2.y]||w1[h2.x][h2.y]==0)&&o[h2.x][h2.y]!=1)
            {
                w1[h2.x][h2.y]=w1[h1.x][h1.y]+1;
                q.push(h2);
            }
        }
    }
}

int main()
{
    f>>n>>m;
    f.getline(v,200);

    min1=100000;
    for(i=1;i<=n;i++)
        {
            f.getline(v,200);
            for(j=0;j<=m;j++)
            {
                if(v[j]=='X')
                    o[i][j+1]=1;
                if(v[j]=='R')
                {
                    rx=i;
                    ry=j+1;
                }
                if(v[j]=='J')
                {
                    jx=i;
                    jy=j+1;
                }
            }
        }


        LeeR();
        LeeJ();
       /*  for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                g<<o[i][j]<<" ";
            g<<"\n";
        }
         g<<"\n";
         for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                g<<w[i][j]<<" ";
            g<<"\n";
        }
         g<<"\n";
         for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                g<<w1[i][j]<<" ";
            g<<"\n";
        }
         g<<"\n";
         */
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
        {
            if(w[i][j]==w1[i][j]&&w[i][j]!=0&&w[i][j]<min1)
            {
                min1=w[i][j];
                di=i;
                dj=j;
            }
        }
        g<<min1<<" "<<di<<" "<<dj;

    return 0;
}