Cod sursa(job #1393278)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 19 martie 2015 11:34:07
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
short N,M,i,j,nr,Rx,Ry,Jx,Jy,min1=31099,minx=110,miny=110;
short dx[8]={1,-1,0,0,-1,-1,1,1},dy[8]={0,0,-1,1,-1,1,-1,1};
short a[105][105],b[105][105];
char sir[10010];

struct elem
{
    short x,y;
};
queue<elem> C;

void lee_a();
void lee_b();
void bordare();

int main()
{
    f>>N>>M;
    f.getline(sir,1);
    for (i=1;i<=N;++i)
    {
        f.getline(sir,10000);
        nr=0;
        //cout<<sir<<'\n';
        for (j=1;j<=M;++j)
        {
            if (sir[nr]=='R')
            {
                a[i][j]=1;
                Rx=i;Ry=j;
            }
            else if (sir[nr]=='J')
            {
                b[i][j]=1;
                Jx=i;Jy=j;
            }
            else if (sir[nr]=='X')
                a[i][j]=b[i][j]=-1;
            ++nr;
        }
    }
    /*for (i=1;i<=N;++i)
    {
        for (j=1;j<=M;++j)
            cout<<b[i][j]<<' ';
        cout<<'\n';
    }
    cout<<"\n\n";*/
    bordare();
    elem A;
    A.x=Rx;A.y=Ry;
    C.push(A);
    lee_a();
    A.x=Jx;A.y=Jy;
    C.push(A);
    lee_b();
    /*for (i=1;i<=N;++i)
    {
        for (j=1;j<=M;++j)
            cout<<b[i][j]<<' ';
        cout<<'\n';
    }
    cout<<"\n\n";*/
    /*for (i=1;i<=N;++i)
    {
        for (j=1;j<=M;++j)
        {
            if (a[i][j]>0)
                --a[i][j];
            if (b[i][j]>0)
                --b[i][j];
            if (a[i][j]==b[i][j])
                cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }*/
    for (i=1;i<=N;++i)
    {
        for (j=1;j<=M;++j)
            {if (a[i][j]>0 && a[i][j]==b[i][j])
            {
                if (a[i][j]<min1)
                    min1=a[i][j],minx=i,miny=j;
                else if (a[i][j]==min1)
                {
                    if (i<minx)
                        minx=i,miny=j;
                    else if (i==minx)
                    {
                        if (j<miny)
                            minx=i,miny=j;
                    }
                }
            }
            //cout<<min1<<' '<<minx<<' '<<miny<<'\n';
            }
    }
    g<<min1<<' '<<minx<<' '<<miny<<'\n';
    /*for (i=1;i<=N;++i)
    {
        for (j=1;j<=M;++j)
            cout<<b[i][j]<<' ';
        cout<<'\n';
    }*/
    f.close();g.close();
    return 0;
}

void lee_a()
{
    while (!C.empty())
    {
        elem A;
        A=C.front();
        C.pop();
        for (int l=0;l<=7;++l)
            if ((a[A.x+dx[l]][A.y+dy[l]]!=-1 && a[A.x+dx[l]][A.y+dy[l]]>a[A.x][A.y]+1) || a[A.x+dx[l]][A.y+dy[l]]==0)
            {
                a[A.x+dx[l]][A.y+dy[l]]=a[A.x][A.y]+1;
                elem B;
                B.x=A.x+dx[l];B.y=A.y+dy[l];
                C.push(B);
            }
    }
}

void lee_b()
{
    while (!C.empty())
    {
        elem A;
        A=C.front();
        C.pop();
        for (int l=0;l<=7;++l)
            if ((b[A.x+dx[l]][A.y+dy[l]]!=-1 && b[A.x+dx[l]][A.y+dy[l]]>b[A.x][A.y]+1) || b[A.x+dx[l]][A.y+dy[l]]==0)
            {
                b[A.x+dx[l]][A.y+dy[l]]=b[A.x][A.y]+1;
                elem B;
                B.x=A.x+dx[l];B.y=A.y+dy[l];
                C.push(B);
            }
    }
}

void bordare()
{
    for (i=0;i<=N+1;++i)
        a[i][0]=b[i][0]=a[i][M+1]=b[i][M+1]=-1;
    for (i=0;i<=M+1;++i)
        a[0][i]=b[0][i]=a[N+1][i]=b[N+1][i]=-1;
}