Cod sursa(job #2187446)

Utilizator MattCMatei Coroiu MattC Data 26 martie 2018 15:26:59
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int MAXN = 105;

int mat[MAXN][MAXN];
int leeR[MAXN][MAXN];
int leeJ[MAXN][MAXN];

queue < pair < int, int > > Q;

int di[] = {-1,-1,-1,0,1,1,1,0};
int dj[] = {-1,0,1,1,1,0,-1,-1};

int n, m;

bool valid(int i, int j)
{
    if (i < 1 || i > n || j < 1 || j > m) return 0;
    if (mat[i][j] == 1 || leeR[i][j]) return 0;
    return 1;
}

bool ok(int i, int j)
{
    if (i < 1 || i > n || j < 1 || j > m) return 0;
    if (mat[i][j] == 1 || leeJ[i][j]) return 0;
    return 1;
}

int main()
{
    int i, j, iR, jR, iJ, jJ, i_nou, j_nou, x, y, tmin = 50005;
    string sir;
    fin >> n >> m;
    for (i = 0; i <= n; ++i)
    {
        getline(fin,sir);
        for (j = 0; j < sir.length(); ++j)
        {
            if (sir[j] == 'R')
            {
                mat[i][j + 1] = 2;
                iR = i;
                jR = j + 1;
            }
            else if (sir[j] == 'J')
            {
                mat[i][j + 1] = 2;
                iJ = i;
                jJ = j + 1;
            }
            else if (sir[j] == 'X')
            {
                mat[i][j + 1] = 1;
            }
            else mat[i][j + 1] = 0;
        }
    }
    Q.push({iR, jR});
    leeR[iR][jR] = leeJ[iJ][jJ] = 1;
    while (!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for (int k = 0; k < 8; ++k)
        {
            i_nou = i + di[k];
            j_nou = j + dj[k];
            if (valid(i_nou,j_nou))
            {
                leeR[i_nou][j_nou] = leeR[i][j] + 1;
                Q.push({i_nou,j_nou});
            }
        }
    }
    Q.push({iJ, jJ});
    while (!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for (int k = 0; k < 8; ++k)
        {
            i_nou = i + di[k];
            j_nou = j + dj[k];
            if (ok(i_nou, j_nou))
            {
                leeJ[i_nou][j_nou] = leeJ[i][j] + 1;
                Q.push({i_nou, j_nou});
            }
        }
    }
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            if (leeR[i][j] == leeJ[i][j] && leeR[i][j])
            {
                if (leeR[i][j] < tmin)
                {
                    tmin = leeR[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    }
    fout << tmin << " " << x << " " << y << "\n";
    return 0;
}