Cod sursa(job #1685844)

Utilizator Tudor_CandeaCandea Tudor Tudor_Candea Data 11 aprilie 2016 21:26:03
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 14.25 kb
#include <fstream>
#include <queue>
#include <string>
using namespace std;

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

struct ro
{
    char c;
    int nr;
}rj[103][103];

queue <int> qx, qy;

char aux[102];
int main()
{
    int n, m,ct=0;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin.get();
        fin.get(aux,101);
        for(int j=0;j<m;j++)
        {
            ct=0;
            if(aux[j]=='X')
            {
                 rj[i][j+1].nr=-1;
                 ct=1;
            }
            if(aux[j]==' ')
            {
                rj[i][j+1].nr=m*n+2;
                ct=1;
            }
            if(aux[j]=='R')
            {
                qx.push(i);
                qy.push(j+1);
                rj[i][j+1].nr=1;
                rj[i][j+1].c='R';
                ct=1;
            }
            if(aux[j]=='J')
            {
                qx.push(i);
                qy.push(j+1);
                rj[i][j+1].nr=1;
                rj[i][j+1].c='J';
                ct=1;
            }
            if(ct==0)
                rj[i][j+1].nr=m*n+2;;
        }
    }
    //int ct1=0;
    int mi1=m*n+1, mi2=m*n+1;
    while(!qx.empty())
    {
        int xv=qx.front();
        qx.pop();
        int yv=qy.front();
        qy.pop();
      //  ct1++;
        int xu=xv;
        int yu=yv-1;
        if(yu>0 and yu<m*n+1)
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
              //          fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
              //          fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
              //          fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
              //          fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv;
        yu=yv+1;
        if(yu>0 and yu<m*n+1)
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
               //         fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                //        fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
                //        fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                //        fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv-1;
        yu=yv;
        if(xu>0 and xu<m*n+1)
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
               //         fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                //        fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv+1;
        yu=yv;
        if(xu>0 and xu<m*n+1)
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
                //        fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                //        fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
                  //      fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv+1;
        yu=yv+1;
        if((yu>0 and yu<m*n+1)and(xu>0 and xu<m*n+1))
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                  //      fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv-1;
        yu=yv+1;
        if((yu>0 and yu<m*n+1)and(xu>0 and xu<m*n+1))
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
           if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                   //     fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
                   //     fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                  //      fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv+1;
        yu=yv-1;
        if((yu>0 and yu<m*n+1)and(xu>0 and xu<m*n+1))
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
                if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
                  //      fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                   //     fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
                   //     fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }

        xu=xv-1;
        yu=yv-1;
        if((yu>0 and yu<m*n+1)and(xu>0 and xu<m*n+1))
        if(rj[xu][yu].nr>rj[xv][yv].nr+1)
        {
            rj[xu][yu].nr=rj[xv][yv].nr+1;
            qx.push(xu);
            qy.push(yu);
            if(rj[xv][yv].c=='R')
                rj[xu][yu].c='R';
            if(rj[xv][yv].c=='J')
                rj[xu][yu].c='J';
        }
        if((rj[xv][yv].c=='R' and rj[xu][yu].c=='J')||(rj[xv][yv].c=='J' and rj[xu][yu].c=='R'))
        {
            if(rj[xv][yv].nr!=rj[xu][yu].nr)
            {
               if(rj[xv][yv].nr>rj[xu][yu].nr)
                {
                    if(xv<mi1)
                    {
                        mi1=xv;
                        mi2=yv;
                      //  fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xv==mi1 and yv<mi2)
                    {
                        mi1=xv;
                        mi2=yv;
                       // fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<mi1)
                    {
                        mi1=xu;
                        mi2=yu;
                 //       fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                    if(xu==mi1 and yu<mi2)
                    {
                        mi1=xu;
                        mi2=yu;
                      //  fout<<mi1<<' '<<mi2<<' '<<ct1<<'\n';
                    }
                }
            }
        }
    }
   /* for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(rj[i][j].nr==-1)
                    fout<<"0"<<' ';
                else
                fout<<rj[i][j].nr<<' ';
            }
            fout<<'\n';
        }
    fout<<'\n';*/

    fout<<rj[mi1][mi2].nr<<' '<<mi1<<' '<<mi2;
    return 0;
}