Cod sursa(job #694734)

Utilizator voicuraduVoicu Radu voicuradu Data 27 februarie 2012 23:09:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 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;
short int n,m,vr[111][111],vj[111][111];

void bfs(ELEMENT x0,short 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[111];
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

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

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;
}