Cod sursa(job #1579409)

Utilizator tqmiSzasz Tamas tqmi Data 24 ianuarie 2016 18:35:53
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <fstream>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int N,M,d1[105][105],d2[105][105],i,j,sol=INT_MAX,soli,solj,X,Y;
char c;
struct koord{int x,y;};
queue <koord> s1,s2;
koord z;
void read()
{
    fin>>N>>M;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            fin>>c;
            if(c=='R')
            {
                z.x=i;
                z.y=j;
                s1.push(z);
            }
            if(c=='J')
            {
                z.x=i;
                z.y=j;
                s2.push(z);
            }
            if(c=='X')
            {
                d1[i][j]=-1;
                d2[i][j]=-1;
            }
        }
    }
}
void bord()
{
    for(i=1;i<=N;i++)
    {
        d1[i][0]=-1;
        d1[i][M+1]=-1;
    }
    for(i=1;i<=M;i++)
    {
        d1[0][i]=-1;
        d1[N+1][i]=-1;
    }
     for(i=1;i<=N;i++)
    {
        d2[i][0]=-1;
        d2[i][M+1]=-1;
    }
    for(i=1;i<=M;i++)
    {
        d2[0][i]=-1;
        d2[N+1][i]=-1;
    }
}
void solve()
{
    bord();
    while(!s1.empty())
    {
        z=s1.front();
        X=z.x;
        Y=z.y;
        if(d1[X-1][Y]==0)
        {
            d1[X-1][Y]=d1[X][Y]+1;
            z.x=X-1;
            z.y=Y;
            s1.push(z);
        }
        if(d1[X-1][Y+1]==0)
        {
            d1[X-1][Y+1]=d1[X][Y]+1;
            z.x=X-1;
            z.y=Y+1;
            s1.push(z);
        }
        if(d1[X][Y+1]==0)
        {
            d1[X][Y+1]=d1[X][Y]+1;
            z.x=X;
            z.y=Y+1;
            s1.push(z);
        }
        if(d1[X+1][Y+1]==0)
        {
            d1[X+1][Y+1]=d1[X][Y]+1;
            z.x=X+1;
            z.y=Y+1;
            s1.push(z);
        }
        if(d1[X+1][Y]==0)
        {
            d1[X+1][Y]=d1[X][Y]+1;
            z.x=X+1;
            z.y=Y;
            s1.push(z);
        }
        if(d1[X+1][Y-1]==0)
        {
            d1[X+1][Y-1]=d1[X][Y]+1;
            z.x=X+1;
            z.y=Y-1;
            s1.push(z);
        }
        if(d1[X][Y-1]==0)
        {
            d1[X][Y-1]=d1[X][Y]+1;
            z.x=X;
            z.y=Y-1;
            s1.push(z);
        }
        if(d1[X-1][Y-1]==0)
        {
            d1[X-1][Y-1]=d1[X][Y]+1;
            z.x=X-1;
            z.y=Y-1;
            s1.push(z);
        }
        s1.pop();
    }
    while(!s2.empty())
    {
        z=s2.front();
        X=z.x;
        Y=z.y;
        if(d2[X-1][Y]==0){d2[X-1][Y]=d2[X][Y]+1;
        z.x=X-1;z.y=Y;s2.push(z);}
        if(d2[X-1][Y+1]==0){d2[X-1][Y+1]=d2[X][Y]+1;
        z.x=X-1;z.y=Y+1;s2.push(z);}
        if(d2[X][Y+1]==0){d2[X][Y+1]=d2[X][Y]+1;
        z.x=X;z.y=Y+1;s2.push(z);}
        if(d2[X+1][Y+1]==0){d2[X+1][Y+1]=d2[X][Y]+1;
        z.x=X+1;z.y=Y+1;s2.push(z);}
        if(d2[X+1][Y]==0){d2[X+1][Y]=d2[X][Y]+1;
        z.x=X+1;z.y=Y;s2.push(z);}
        if(d2[X+1][Y-1]==0){d2[X+1][Y-1]=d2[X][Y]+1;
        z.x=X+1;z.y=Y-1;s2.push(z);}
        if(d2[X][Y-1]==0){d2[X][Y-1]=d2[X][Y]+1;
        z.x=X;z.y=Y-1;s2.push(z);}
        if(d2[X-1][Y-1]==0){d2[X-1][Y-1]=d2[X][Y]+1;
        z.x=X-1;z.y=Y-1;s2.push(z);}
        s2.pop();
    }
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            if(d1[i][j]==d2[i][j] && d1[i][j]>0 && d1[i][j]<sol)
            {
                sol=d1[i][j];
                soli=i;
                solj=j;
            }
        }
    }
}
void print()
{
    fout<<sol<<" "<<soli<<" "<<solj<<"\n";
}

int main()
{
    read();
    solve();
    print();
    return 0;
}