Cod sursa(job #2515361)

Utilizator luchiancristianLuchian Cristian luchiancristian Data 28 decembrie 2019 13:50:11
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");

struct prec {
    int x, y;
} mat[110][110];

int a[110][110],n,m,x[10010],y[10010],x1,x2,y1,y2,sf,i,j;
char s[110];

int solx[10010];
int soly[10010];
int soltotal;

void reconstituiretraseu(int lin, int col)
{
    if(mat[lin][col].x == 0)
    {
        soltotal++;
        solx[soltotal] = lin;
        soly[soltotal] = col;
    }
    else
    {
        reconstituiretraseu(mat[lin][col].x, mat[lin][col].y);

        soltotal++;
        solx[soltotal] = lin;
        soly[soltotal] = col;
    }
}

int main()
{
    in>>n>>m;
    for(i=0;i<=n+1;++i)
        a[i][0]=a[i][m+1]=-1;
    for(j=0;j<=m+1;++j)
        a[0][j]=a[n+1][j]=-1;
    for(i=1;i<=n;++i)
    {
        in.get();
        in.get(s,110);
        for(j=0;j<m;++j)
        {
            if(s[j]=='X')
                a[i][j+1]=-1;
            if(s[j]=='R')
            {
                x1=i;
                y1=j+1;
            }
            if(s[j]=='J')
            {
                x2=i;
                y2=j+1;
            }
            s[j]=0;
        }
    }
    x[1]=x1;
    y[1]=y1;
    sf=1;
    for(i=1;x[i];++i)
    {
        int d1[]={0,0,1,1,1,-1,-1,-1},d2[]={1,-1,0,-1,1,1,0,-1};
        for(j=0;j<8;++j)
        {
            if(a[x[i]+d1[j]][y[i]+d2[j]]==0)
            {
                a[x[i]+d1[j]][y[i]+d2[j]]=a[x[i]][y[i]]+1;
                sf++;
                x[sf]=x[i]+d1[j];
                y[sf]=y[i]+d2[j];

                int xnou = x[i] + d1[j];
                int ynou = y[i] + d2[j];

                if(mat[xnou][ynou].x != 0)
                {
                    int xvechi = mat[xnou][ynou].x;
                    int yvechi = mat[xnou][ynou].y;

                    // (x[i], y[i]) -> xnou, you
                    // xvechi, yvechi -> xnou, ynou

                    if(xvechi > x[i] || (xvechi == x[i] && yvechi > y[i]))
                    {
                        mat[xnou][ynou].x = x[i];
                        mat[xnou][ynou].y = y[i];
                    }
                }
                else
                {
                    mat[xnou][ynou].x = x[i];
                    mat[xnou][ynou].y = y[i];
                }
            }
        }
    }
    mat[x1][y1].x = mat[x1][y1].y = 0;
    a[x1][y1] = 0;
    /*for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
            out<<a[i][j]<<' ';
        out<<'\n';
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            out << "( " << mat[i][j].x << ", " << mat[i][j].y << " ) ";
        }

        out << '\n';
    }*/

    reconstituiretraseu(x2, y2);

    out<<(a[x2][y2]+2)/2<<' ';
    if(soltotal%2==1)
        out<<solx[soltotal/2+1]<<' '<<soly[soltotal/2+1];
    else
    {
        if(solx[soltotal/2]<solx[soltotal/2+1])
        {
            out<<solx[soltotal/2]<<' '<<soly[soltotal/2];
            return 0;
        }
        if(solx[soltotal/2]>solx[soltotal/2+1])
        {
            out<<solx[soltotal/2+1]<<' '<<soly[soltotal/2+1];
            return 0;
        }
        if(soly[soltotal/2]<soly[soltotal/2+1])
        {
            out<<solx[soltotal/2]<<' '<<soly[soltotal/2];
            return 0;
        }
        out<<solx[soltotal/2+1]<<' '<<soly[soltotal/2+1];
    }
    return 0;
}