Cod sursa(job #887303)

Utilizator Becu15Coca Cola Octavian Becu15 Data 23 februarie 2013 17:55:34
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <stdio.h>
struct pozitii { int lin,col; } v,p,c[10000],g[400];
int mat[101][101];
int n,m,x1,x2,y1,y2;
const int dx[]={-1,-1,0,1,1,1,0,-1}, dy[]={0,1,1,1,0,-1,-1,-1};
void citire ()
{
    int i,j;
    char ceva;
    scanf ("%d %d",&n,&m);
    scanf ("%c",&ceva);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            scanf ("%c",&ceva);
            if (int(ceva)==10 && j==m)
                ceva=' ';
            if (int(ceva)==10)
                scanf ("%c",&ceva);
            if (int(ceva)==32) //" "
                mat[i][j]=0;
            else if (int(ceva)==88) //"X"
                mat[i][j]=-1;
            else if (int(ceva)==82) //"R"
            {
                mat[i][j]=1;
                x1=i;y1=j;
            }
            else if (int(ceva)==74) //"J"
            {
                mat[i][j]=0;
                x2=i;y2=j;
            }
        }
    }
}
int matt()
{
    int i,j,k,prim=0,ultim=0,nrpasi=0;
    for (i=0;i<=m+1;i++)
        mat[0][i]=mat[n+1][i]=-1;
    for (i=0;i<=n+1;i++)
        mat[i][0]=mat[i][m+1]=-1;
    c[0].lin=x1;
    c[0].col=y1;
    while (mat[x2][y2]==0 && prim<=ultim)
    {
        p.lin=c[prim].lin;
        p.col=c[prim].col;
        prim++;
        for (k=0;k<8;k++)
        {
            v.lin=p.lin+dx[k];
            v.col=p.col+dy[k];
            if (mat[v.lin][v.col]==0)
            {
                mat[v.lin][v.col]=mat[p.lin][p.col]+1;
                ultim++;
                c[ultim].lin=v.lin;
                c[ultim].col=v.col;
                if (v.lin == x2 && v.col == y2)
                    nrpasi=mat[v.lin][v.col];
            }
        }
    }
    return nrpasi;
}
int cauta (int x)
{
    int i=0,j,prim=0,ultim=0,k;
    c[0].lin=x2;
    c[0].col=y2;
    while (mat[x1][y1]==1 && prim<=ultim)
    {
        p.lin=c[prim].lin;
        p.col=c[prim].col;
        prim++;
        for (k=0;k<8;k++)
        {
            v.lin=p.lin+dx[k];
            v.col=p.col+dy[k];
            if (mat[v.lin][v.col]>=0)
            {
                ultim++;
                c[ultim].lin=v.lin;
                c[ultim].col=v.col;
                if (v.lin == x1 && v.col == y1)
                    mat[v.lin][v.col]=-1;
                if (mat[v.lin][v.col]==x)
                {
                    g[i].lin=v.lin;
                    g[i].col=v.col;
                    i++;
                    mat[v.lin][v.col]=-mat[v.lin][v.col];
                }
            }
        }
    }
    return i;
}
void pozfinala(int lim)
{
    int i,minl=101,minc=101;
    for (i=0;i<lim;i++)
        if (g[i].lin<minl)
            minl=g[i].lin;
    for (i=0;i<lim;i++)
        if (g[i].lin==minl)
            if (g[i].col<minc)
                minc=g[i].col;
    printf ("%d %d %d",-mat[minl][minc],minl,minc);
}
void afisare (int num)
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            printf ("%d",mat[i][j]);
        }
        printf ("\n");
    }
    for (i=0;i<num;i++)
    {
        printf ("%d %d\n",g[i].lin,g[i].col);
    }

}
int main()
{
    int i,x,xx,num;
    freopen ("rj.in","r",stdin);
    freopen ("rj.out","w",stdout);
    citire();
    x=matt();
    xx=(x+1)/2;
    num=cauta(xx);
    //afisare(num);
    pozfinala(num);
    return 0;
}