Cod sursa(job #1687411)

Utilizator Tudor_CandeaCandea Tudor Tudor_Candea Data 12 aprilie 2016 20:50:04
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 15.5 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,ma=m*n*n*m;
    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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                    //            fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                    //            fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                   //             fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                   //             fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                     //           fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                      //          fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                      //          fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                      //          fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                   //             fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                       //         fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                      //          fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                       //         fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                       //         fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                       //         fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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)
                    {
                        if(yv<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xv][yv].nr;
                                mi1=xv;
                                mi2=yv;
                       //         fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<ct1<<'\n';
                            }
                        }
                    }
                }
                if(rj[xv][yv].nr<rj[xu][yu].nr)
                {
                    if(xu<=mi1)
                    {
                        if(yu<mi2)
                        {
                            if(rj[xv][yv].nr<ma)
                            {
                                ma=rj[xu][yu].nr;
                                mi1=xu;
                                mi2=yu;
                        //        fout<<mi1<<' '<<mi2<<' '<<rj[mi1][mi2].nr<<' '<<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;
}