Cod sursa(job #2297694)

Utilizator ioana.jianuIoana Jianu ioana.jianu Data 6 decembrie 2018 11:41:47
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int pozL[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int pozC[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const int NMAX = 100;
struct ura {int l, c;};
ura coada[NMAX * NMAX + 1];
char a[NMAX + 1][NMAX + 1], sir[NMAX + 1];
int lee[2][NMAX + 1][NMAX + 1];
int n, m;

void functie (int om, int tmax, int x, int y) {
    int in, sf, lc, cc, i;
    in = 1;
    sf = 1;
    coada[1].l = x;
    coada[1].c = y;
    while (in <= sf) {
        for (i = 0; i < 8; i++) {
            lc = coada[in].l + pozL[i];
            cc = coada[in].c + pozC[i];
            if (a[lc][cc] == ' ' && lee[om][lc][cc] == 0) {
                lee[om][lc][cc] = lee[om][coada[in].l][coada[in].c] + 1;
               // if (lee[om][lc][cc] < tmax) {
                    sf++;
                    coada[sf].l = lc;
                    coada[sf].c = cc;
               //}
            }
        }
        in++;
    }
}

void curata (int om) {
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            lee[om][i][j] = 0;
}


int main() {

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

    int i, j, timp, st, dr, retine, cf, lf, pp, xr, xj, yr, yj, minim;
    char inutil;

    scanf ("%d%d ", &n, &m);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++)
            scanf ("%c", &a[i][j]);
        scanf ("%c", &inutil);
    }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            if (a[i][j] == 'R') {
                xr = i;
                yr = j;
            }
            if (a[i][j] == 'J') {
                xj = i;
                yj = j;
            }
        }

    for (i = 0; i <= n + 1; i++)
        a[i][0] = a[i][m + 1] = 'X';
    for (j = 0; j <= m + 1; j++)
        a[0][j] = a[n + 1][j] = 'X';

    /*st = 1;
    dr = n * m;
    while (st <= dr) {
        timp = (st + dr) / 2;*/
        functie (0, timp, xr, yr);
        functie (1, timp, xj, yj);

      /*  pp = 0;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                if (lee[0][i][j] == lee[1][i][j] && pp == 0) {
                    lf = i;
                    cf = j;
                    pp = 1;
                }
        if (pp == 1) {
            retine = timp;
            st = timp + 1;
        }
        else
            dr = timp - 1;
        curata (1);
        curata (2);*/

      /*  for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++)
                printf ("%d ", lee[0][i][j]);
            printf ("\n");
        }
        printf ("\n");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++)
                printf ("%d ", lee[1][i][j]);
            printf ("\n");
        }*/

        minim = n * m + 1;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                if (lee[0][i][j] > 0 && lee[0][i][j] == lee[1][i][j] && lee[0][i][j] < minim) {
                    minim = lee[0][i][j];
                    lf = i;
                    cf = j;
                }
    //}

    printf ("%d %d %d", minim + 1, lf, cf);

    return 0;
}