Cod sursa(job #1910505)

Utilizator Storm_FireFox1Matei Gardus Storm_FireFox1 Data 7 martie 2017 17:13:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <fstream>
#include <string>

using namespace std;

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

const short NMAX = 100;
const short nd = 8;
const short dx[nd] = {0, 0, -1, 1, 1, -1, -1, 1};
const short dy[nd] = {1, -1, 0, 0, 1, 1, -1, -1};

short romeo[NMAX + 2][NMAX + 2], julieta[NMAX + 2][NMAX + 2], n, m;
short qx[NMAX * NMAX + 1], qy[NMAX * NMAX + 1];

void BFSr(int x, int y)
{
    for(int i = 0; i <= n + 1; i++)
    {
        romeo[i][0] = -1;
        romeo[i][m + 1] = -1;
    }
    for(int j = 0; j <= m + 1; j++)
    {
        romeo[0][j] = -1;
        romeo[n + 1][j] = -1;
    }
    romeo[x][y] = 1;
    qx[1] = x;
    qy[1] = y;
    int qb = 1, qe = 1;
    while(qb <= qe)
    {
        int bx = qx[qb], by = qy[qb];
        qb++;
        for(int i = 0; i < nd; i++)
        {
            int xn = bx + dx[i], yn = by + dy[i];
            if(romeo[xn][yn] == 0)
            {
                romeo[xn][yn] = romeo[bx][by] + 1;
                ++qe;
                qx[qe] = xn;
                qy[qe] = yn;
            }
        }
    }
}

void BFSj(int x, int y)
{
    for(int i = 0; i <= n + 1; i++)
    {
        julieta[i][0] = -1;
        julieta[i][m + 1] = -1;
    }
    for(int j = 0; j <= m + 1; j++)
    {
        julieta[0][j] = -1;
        julieta[n + 1][j] = -1;
    }
    julieta[x][y] = 1;
    qx[1] = x;
    qy[1] = y;
    int qb = 1, qe = 1;
    while(qb <= qe)
    {
        int bx = qx[qb], by = qy[qb];
        qb++;
        for(int i = 0; i < nd; i++)
        {
            int xn = bx + dx[i], yn = by + dy[i];
            if(julieta[xn][yn] == 0)
            {
                julieta[xn][yn] = julieta[bx][by] + 1;
                ++qe;
                qx[qe] = xn;
                qy[qe] = yn;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    string s;
    getline(fin, s);
    int rx, ry, jx, jy;
    for(int i = 1; i <= n; ++i) {
        getline(fin, s);
        for(int j = 0; j < int(s.size()); ++j) {
            if ( s[j] == 'X' ) {
                romeo[i][j + 1] = -1;
                julieta[i][j + 1] = -1;
            }
            if (s[j] == 'R') {
                rx = i;
                ry = j + 1;
            }
            if (s[j] == 'J') {
                jx = i;
                jy = j + 1;
            }
        }
    }
    BFSr(rx, ry);
    BFSj(jx, jy);
    int tmin = (NMAX + 1)*(NMAX + 1), solx, soly;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(romeo[i][j] > 0 && julieta[i][j] > 0 && max(romeo[i][j], julieta[i][j]) < tmin) {
                tmin = max(romeo[i][j], julieta[i][j]);
                solx = i;
                soly = j;
            } else if(romeo[i][j] > 0 && julieta[i][j] > 0 && max(romeo[i][j], julieta[i][j]) == tmin && solx > i) {
                tmin = max(romeo[i][j], julieta[i][j]);
                solx = i;
                soly = j;
            } else if(romeo[i][j] > 0 && julieta[i][j] > 0 && max(romeo[i][j], julieta[i][j]) == tmin && solx == i && soly > j) {
                tmin = max(romeo[i][j], julieta[i][j]);
                solx = i;
                soly = j;
            }
        }
    }
    fout << tmin << " " << solx << " " << soly;
    return 0;
}