Cod sursa(job #891360)

Utilizator Becu15Coca Cola Octavian Becu15 Data 25 februarie 2013 16:13:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.45 kb
#include <stdio.h>
struct pozitii { int lin,col; } v,p,c[10000],g[100],poz[1000];
int mat[101][101];
int n,m,x1,x2,y1,y2,en=0;
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 matr()
{
    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=7;k>=0;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];
            }
        }
    }
    for (i=0;i<=10000;i++)
    {
        c[i].lin=0;
        c[i].col=0;
    }
    return nrpasi;
}
int pozitii(int x)
{
    int i,j,k=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (mat[i][j]==x)
            {
                poz[k].lin=i;
                poz[k].col=j;
                k++;
            }
    return k;
}
void zero(int x)
{
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (mat[i][j]!=-1)
                mat[i][j]=0;
}
int estedeja (int linie, int coloana)
{
    int i,ok;
    for (i=0;i<en;i++)
        if (poz[i].lin==linie && poz[i].col==coloana) return 1;
    return 0;
}
int matj (int x)
{
    int i=0,j=0,prim=0,ultim=0,k;
    c[0].lin=x2;
    c[0].col=y2;
    mat[x1][y1]=0;
    mat[x2][y2]=1;
    while (mat[x1][y1]==0 && prim<=ultim)
    {
        p.lin=c[prim].lin;
        p.col=c[prim].col;
        prim++;
        for (k=7;k>=0;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 (mat[v.lin][v.col]==x && estedeja(v.lin,v.col)==1)
                {
                    //printf ("i = %d\n",i);
                    g[i].lin=v.lin;
                    g[i].col=v.col;
                    //printf ("\ng[%d]=%d %d\n",i,g[i].lin,g[i].col);
                    i++;

                    //mat[v.lin][v.col]=-mat[v.lin][v.col];
                }

            }
            if (v.lin == x1 && v.col == y1)
                return i;
        }
    }
    //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");
    }
    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();
    //afisare (num);
    x=matr();
    xx=(x+1)/2;
    //mat[x2][y2]=1;
    en=pozitii(xx);
    //afisare (num);
    //for (i=0;i<en;i++)
    //    printf ("%d %d\n",poz[i].lin,poz[i].col);
    zero(xx);
    //afisare (num);
    num=matj(xx);
    //afisare(num);
    pozfinala(num);
    return 0;
}