Cod sursa(job #1502823)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 15 octombrie 2015 00:25:03
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
# include <cstdio>
# include <queue>
# include <climits>

using namespace std;

const int MAX = 100 + 5;

int ri, rf, ji, jf, Min = INT_MAX, poz1, poz2, n, m;
int r[MAX][MAX], J[MAX][MAX];
int dx[8]= {0,0,-1,1,1,1,-1,-1};
int dy[8]= {1,-1,0,0,1,-1,1,-1};
char x;

queue < pair <int, int> > Q;


void lee (int a[MAX][MAX], int xi, int xf)
{
    Q.push(make_pair(xi,xf));

    int i, xx, yy, val = 0;

    while (!Q.empty())
    {

        pair <int, int> X = Q.front();

        for (i = 0; i < 8; i++)
        {
            xx = X.first + dx[i];
            yy = X.second + dy[i];

            if (a[xx][yy] == 0)
            {
                Q.push(make_pair(xx,yy));
                a[xx][yy]  = a[X.first][X.second] + 1;
            }
        }
        Q.pop();
    }

}
void bord()
{
    int i, j;
    for  (i = 0; i <= n + 1; i++)
        for (j = 0; j <= m + 1; j++)
            if (i == 0 || j == 0 || i == n + 1 || j == m + 1)
            {
                r[i][j] = -1;
                J[i][j] = -1;
            }
}


int main ()

{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    int i, j;

    scanf("%d%d", &n, &m);

    for (i = 1; i <= n; i++)
    {
        scanf("%c", &x);
        for (j = 1; j <= m; j++)
        {
            scanf("%c", &x);
            if (x == ' ') r[i][j] = J[i][j] = 0;
            if (x == 'X') r[i][j] = J[i][j] = -1;
            if (x == 'R') ri = i, rf = j;
            if (x == 'J') ji = i, jf = j;
        }
    }

    bord();
    lee (r, ri, rf);
    lee (J, ji, jf);

    for ( i = 1; i <= n; i++)
        for ( j = 1; j <= m; j++)
        {
            if (r[i][j] == J[i][j] && r[i][j] != -1 && r[i][j] != 0 && i != ri && j != rf && i != ji && j != jf)
                if (Min > r[i][j])
                {
                    Min = r[i][j];
                    poz1 = i;
                    poz2 = j;
                }
        }

    printf("%d %d %d", Min + 1, poz1 , poz2);

    return 0;
}