Cod sursa(job #1580665)

Utilizator stefii_predaStefania Preda stefii_preda Data 25 ianuarie 2016 23:37:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <cstdio>
#define N 104
using namespace std;
int rom[N][N], jul[N][N];

struct coada
{
    int lin;
    int col;
};
coada c[N*N];

int dx[]= {-1, -1, -1, 1, 1, 1, 0, 0};
int dy[]= {-1, 0, 1, -1, 0, 1, -1, 1};
int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    int n, m, i, j;
    scanf("%d %d\n", &n, &m);
    char a;
    int xr, yr, xj, yj;//indici romeo si julieta
    for(i= 1; i<= n; i++)
    {
        for(j= 1; j<= m; j++)
        {
            scanf("%c", &a);
            if(a=='R')
            {
                rom[i][j]= 1;
                xr= i;
                yr= j;

            }
            if(a=='J')
            {
                jul[i][j]= 1;
                xj= i;
                yj= j;
            }
            if(a=='X')rom[i][j]= jul[i][j]= -1;
        }
        scanf("\n");
    }
    //bordare
    for(i= 0; i<= m+1; i++) rom[0][i]= rom[n+1][i]= jul[0][i]= jul[n+1][i]= -1;
    for(i= 0; i<= n+1; i++) rom[i][0]= rom[i][m+1]= jul[i][0]= jul[i][m+1]= -1;

    //lee pe matricea lui romeo
    int p= 1, u= 1, x, y;
    c[1].lin= xr;
    c[1].col= yr;

    while(p<= u)
    {
        x= c[p].lin;
        y= c[p].col;
        p++;
        for(i= 0; i<8; i++)
        {
            if(rom[x+dx[i]][y+dy[i]] == 0)
            {
                u++;
                c[u].lin= x+ dx[i];
                c[u].col= y+ dy[i];
                rom[x+dx[i]][y+dy[i]]= rom[x][y]+ 1;
            }
        }
    }
    /*for(i= 1; i<= n; i++)
    {
        for(j= 1; j<= m; j++)
            printf("%d ", rom[i][j]);
        printf("\n");
    */

    p= u= 1;
    c[1].lin= xj;
    c[1].col= yj;
    while(p<= u)
    {
        x= c[p].lin;
        y= c[p].col;
        p++;
        for(i= 0; i<8; i++)
        {
            if(jul[x+dx[i]][y+dy[i]] == 0)
            {
                u++;
                c[u].lin= x+ dx[i];
                c[u].col= y+ dy[i];
                jul[x+dx[i]][y+dy[i]]= jul[x][y]+ 1;
            }
        }
    }
    int tmin= 2000000000, xmin, ymin;

    for(i= 1; i<= n; i++)
        for(j= 1; j<= m; j++)
            if(rom[i][j]==jul[i][j] && rom[i][j] >0)
            {
                if(rom[i][j]<= tmin)
                {
                    tmin= rom[i][j];
                    xmin= i;
                    ymin= j;
                }
            }
    printf("%d %d %d", tmin, xmin, ymin);




    return 0;
}