Cod sursa(job #694675)

Utilizator voicuraduVoicu Radu voicuradu Data 27 februarie 2012 22:39:45
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<cstdio>
#include<queue>
using namespace std;
const int dlin[]={-1,-1,-1,0,1,1,1,0};
const int dcol[]={-1,0,1,1,1,0,-1,-1};
const int N=111;
struct ELEMENT
{
    int ln,cl;
};
queue <ELEMENT> a;

ELEMENT pr,pj;
int n,m,vr[111][111],vj[111][111];

void bfs(ELEMENT x0,int b[][N])
{
    int i;
    ELEMENT x,y;
    a.push(x0);
    b[x0.ln][x0.cl]=1;
    while(!a.empty())
    {
        x=a.front();
        a.pop();
        for(i=0;i<8;i++)
            {
                y.ln=x.ln+dlin[i];
                y.cl=x.cl+dcol[i];
                if(b[y.ln][y.cl]==-1)
                    {
                        a.push(y);
                        b[y.ln][y.cl]=1+b[x.ln][x.cl];
                    }
            }
    }
}

void read()
{
    int i,j;
    char s;
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            {
                scanf("%c",&s);
                if(s==' ')
                    vr[i][j]=vj[i][j]=-1;
                if(s=='X')
                    vr[i][j]=vj[i][j]=-2;
                if(s=='R')
                    {
                    pr.ln=i;
                    pr.cl=j;
                    }
                if(s=='J')
                    {
                        pj.ln=i;
                        pj.cl=j;
                    }
            }
        scanf("\n");
    }
}

void rez()
{
    int i,j,min,minx,miny;

    for(i=0;i<=n+1;i++)
        vr[i][0]=vr[i][m+1]=vj[i][0]=vj[i][m+1]=-2;
    for(j=0;j<=m+1;j++)
        vr[0][j]=vr[n+1][j]=vj[0][j]=vj[n+1][j]=-2;

    min=n*m;
    bfs(pr,vr);
    bfs(pj,vj);

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(vr[i][j]==vj[i][j] && vr[i][j]<min && vr[i][j]>0)
                {
                    min=vr[i][j];
                    minx=i;
                    miny=j;
                }
   /* for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            printf("%d      ",vr[i][j]);
        printf("\n");
    }
    printf("/////////////////////\n");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            printf("%d      ",vj[i][j]);
        printf("\n");
    }*/

    printf("%d %d %d\n",min,minx,miny);
}

int main()
{
    read();
    rez();
    return 0;
}