Cod sursa(job #1456953)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 2 iulie 2015 14:17:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.3 kb
#include <fstream>
#include <queue>
#include <string>

using namespace std;

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

struct pozitie
{
    int i;
    int j;
};

pozitie pr, pj;
pozitie pc, pu;

queue <pozitie> q;

int a[101][101];

int oro[101][101];
int oju[101][101];

string x[101];

int main()
{
    int n, m;
    int i, j;
    int minim=100000000;
    int imin=0, jmin=0;

    fin >> n >> m;

    for(i=0; i<=n; i++)
        getline(fin, x[i]);

    for(i=0; i<=n; i++)
        for(j=0; j<m; j++)
        {
            if(x[i][j]==' ')
                a[i][j+1]=0;
            if(x[i][j]=='X')
                a[i][j+1]=1;
            if(x[i][j]=='R')
            {
                a[i][j+1]=0;
                pr.i=i;
                pr.j=j+1;
            }
            if(x[i][j]=='J')
            {
                a[i][j+1]=0;
                pj.i=i;
                pj.j=j+1;
            }
        }

    for(j=0; j<=m+1; j++)
    {
        a[0][j]=1;
        a[n+1][j]=1;
    }
    for(i=0; i<=n+1; i++)
    {
        a[i][0]=1;
        a[i][m+1]=1;
    }

    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            oro[i][j]=10001;
            oju[i][j]=10001;
        }

    oro[pr.i][pr.j]=1;
    q.push(pr);

    while(!q.empty())
    {
        pc=q.front();q.pop();

        pu.i=pc.i; pu.j=pc.j+1;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i; pu.j=pc.j-1;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i-1; pu.j=pc.j;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i+1; pu.j=pc.j;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i+1; pu.j=pc.j+1;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i-1; pu.j=pc.j-1;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i-1; pu.j=pc.j+1;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i+1; pu.j=pc.j-1;
        if(a[pu.i][pu.j]==0)
            if(oro[pu.i][pu.j]>1+oro[pc.i][pc.j])
            {
                oro[pu.i][pu.j]=1+oro[pc.i][pc.j];
                q.push(pu);
            }
    }

    oju[pj.i][pj.j]=1;
    q.push(pj);

    while(!q.empty())
    {
        pc=q.front();q.pop();

        pu.i=pc.i; pu.j=pc.j+1;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i; pu.j=pc.j-1;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i-1; pu.j=pc.j;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i+1; pu.j=pc.j;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i+1; pu.j=pc.j+1;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i-1; pu.j=pc.j-1;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i-1; pu.j=pc.j+1;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
        pu.i=pc.i+1; pu.j=pc.j-1;
        if(a[pu.i][pu.j]==0)
            if(oju[pu.i][pu.j]>1+oju[pc.i][pc.j])
            {
                oju[pu.i][pu.j]=1+oju[pc.i][pc.j];
                q.push(pu);
            }
    }

    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(oro[i][j]==oju[i][j] && oro[i][j]<minim)
            {
                minim=oro[i][j];
                imin=i;
                jmin=j;
            }

    fout << minim << " " << imin << " " << jmin;

    return 0;
}