Cod sursa(job #881027)

Utilizator mads2194FMI - Andrei Stroe mads2194 Data 17 februarie 2013 17:13:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <cstdio>
#include <queue>

#define N 102

using namespace std;

bool map[N][N];
int dR[N][N],dJ[N][N];
int n,m;

const int dlin[] = {1,-1,0,0,1,-1,1,-1};
const int dcol[] = {0,0,1,-1,1,1,-1,-1};

struct elem
{
    int lin,col;
} res;

queue <elem> qR,qJ;

bool accesibil(elem p)
{
    if(map[p.lin][p.col]) return 0;
    if(p.lin>=n) return 0;
    if(p.lin<0) return 0;
    if(p.col>=m) return 0;
    if(p.col<0) return 0;
    return 1;
}

void read()
{
    char c[102];
    elem p;
    scanf("%d %d\n",&n,&m);
    for(int i=0;i<n;++i)
    {
        gets(c);
        for(int j=0;j<m;++j)
        {
        if(c[j] == 'X') map[i][j]=1;
        //else if(c[j] == ' ') ;
        else if(c[j]== 'R')
            {
                p.col=j, p.lin=i;
                qR.push(p);
                dR[i][j]=1;
                //map[i][j]=1;
            }
        else if(c[j]== 'J')
            {
                p.col=j, p.lin=i;
                qJ.push(p);
                dJ[i][j]=1;
                //map[i][j]=2;
            }
        }
    }
}

elem run()
{
    elem a,b;

    while(! qR.empty())
    {
        a=qR.front();
        qR.pop();

        for(int i=0;i<8;++i)
        {
            b.col = a.col+dcol[i];
            b.lin = a.lin+dlin[i];
            if(accesibil(b) && dR[b.lin][b.col]==0)
            {
                    qR.push(b);
                    dR[b.lin][b.col] = dR[a.lin][a.col]+1;
            }
        }
    }

    while(! qJ.empty())
    {
        a=qJ.front();
        qJ.pop();

        for(int i=0;i<8;++i)
        {
            b.col = a.col+dcol[i];
            b.lin = a.lin+dlin[i];
            if(accesibil(b) && dJ[b.lin][b.col]==0)
            {
                    qJ.push(b);
                    dJ[b.lin][b.col] = dJ[a.lin][a.col]+1;
            }
        }
    }

    int min = 99999;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        if(dR[i][j]>0)
            if(dR[i][j]==dJ[i][j])
                if(dR[i][j]<min)
                {
                    min=dR[i][j];
                    a.lin = i;
                    a.col = j;
                    //printf("f ");
                }
    return a;
}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    read();

    res = run();

    /*for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            printf("%d ",dR[i][j]);
        printf("\n");
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            printf("%d ",dJ[i][j]);
        printf("\n");
    }*/
    printf("%d %d %d",dR[res.lin][res.col],1+res.lin,1+res.col);
    return 0;
}