Cod sursa(job #1984916)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 26 mai 2017 15:45:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <bits/stdc++.h>
#define DMAX 105
#define CMAX 10010

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

struct poz {short int x, y;} romeo, julieta, c[CMAX];
short int aux1[DMAX][DMAX], aux2[DMAX][DMAX];
char a[DMAX][DMAX]; int m, n;
short int Move[2][8] = {{-1, -1, 0, 1, 1,  1,  0, -1},
                        { 0,  1, 1, 1, 0, -1, -1, -1}};

void out()
{
    int i, j, xMin, yMin, tMin = 618618;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            if (aux1[i][j] == aux2[i][j] && 0 < aux1[i][j] && aux1[i][j] < tMin)
            {
                tMin = aux1[i][j];
                xMin = i; yMin = j;
            }
    fout << tMin << ' ' << xMin << ' ' << yMin << '\n';
    fout.close();
}

void lee2()
{
    int i, j, I, J, p, u, P, U, pas, nrVecini;
    c[1] = julieta; p = u = 1;
    aux2[c[1].x][c[1].y] = 1;
    for (pas = 2; true; pas++)
    {
        nrVecini = 0;
        P = p; U = u;
        for (i = P; i <= U; i++)
            for (j = 0; j < 8; j++)
                if (a[c[i].x + Move[0][j]][c[i].y + Move[1][j]] != 'X' && !aux2[c[i].x + Move[0][j]][c[i].y + Move[1][j]])
                {
                    if (!nrVecini)
                        p = i;
                    nrVecini++;
                    aux2[c[i].x + Move[0][j]][c[i].y + Move[1][j]] = pas;
                    c[++u].x = c[i].x + Move[0][j];
                    c[u].y = c[i].y + Move[1][j];
                }
        if (!nrVecini)
            break;
    }
}

void lee1()
{
    int i, j, I, J, p, u, P, U, pas, nrVecini;
    c[1] = romeo; p = u = 1;
    aux1[c[1].x][c[1].y] = 1;
    for (pas = 2; true; pas++)
    {
        nrVecini = 0;
        P = p; U = u;
        for (i = P; i <= U; i++)
            for (j = 0; j < 8; j++)
                if (a[c[i].x + Move[0][j]][c[i].y + Move[1][j]] != 'X' && !aux1[c[i].x + Move[0][j]][c[i].y + Move[1][j]])
                {
                    if (!nrVecini)
                        p = i;
                    nrVecini++;
                    aux1[c[i].x + Move[0][j]][c[i].y + Move[1][j]] = pas;
                    c[++u].x = c[i].x + Move[0][j];
                    c[u].y = c[i].y + Move[1][j];
                }
        if (!nrVecini)
            break;
    }
}

void in()
{
    int i, j;
    char enter;
    fin >> m >> n;
    for (i = 1; i <= m; i++)
    {
        fin.get(enter);
        for (j = 1; j <= n; j++)
        {
            fin.get(a[i][j]);
            if (a[i][j] == 'R')
                romeo.x = i, romeo.y = j;
            else
                if (a[i][j] == 'J')
                    julieta.x = i, julieta.y = j;
        }
    }
    for (i = 0; i <= m + 1; i++)
        aux1[i][0] = aux1[i][n + 1] = aux2[i][0] = aux2[i][n + 1] = -1;
    for (j = 0; j <= n + 1; j++)
        aux1[0][j] = aux1[m + 1][j] = aux2[0][j] = aux2[m + 1][j] = -1;
}

int main()
{
    in();
    lee1();
    lee2();
    out();
    return 0;
}