Cod sursa(job #2242318)

Utilizator AndreiJJIordan Andrei AndreiJJ Data 18 septembrie 2018 13:17:22
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <fstream>
#include <queue>
using namespace std;
queue < pair <short, short> > q;
char c[105][105];
short rom[105][105], jul[105][105];
short n, m;
short dx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
short dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
const short oo = 20000;
void Read ()
{
    ifstream fin ("rj.in");
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; i++)
        fin.getline(c[i] + 1, 101);
}
void Initiate ()
{
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            rom[i][j] = jul[i][j] = oo;
}
void Board ()
{
    short i, j;
    for (i = 0; i <= n + 1; i++)
        c[i][0] = c[i][m + 1] = 'X';
    for (j = 0; j <= m + 1; j++)
        c[0][j] = c[n + 1][j] = 'X';
}
void LeeR ()
{
    while (!q.empty())
        q.pop();
    short i, j, k, x, y;
    bool OK = true;
    for (i = 1; i <= n && OK; i++)
        for (j = 1; j <= m && OK; j++)
            if (c[i][j] == 'R')
            {
                q.push({i, j});
                rom[i][j] = 1;
                OK = false;
            }
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0; k <= 7; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (c[x][y] == ' ' && rom[x][y] > 1 + rom[i][j])
            {
                rom[x][y] = 1 + rom[i][j];
                q.push({x, y});
            }
        }
    }
}
void LeeJ ()
{
    while (!q.empty())
        q.pop();
    short i, j, k, x, y;
    bool OK = true;
    for (i = 1; i <= n && OK; i++)
        for (j = 1; j <= m && OK; j++)
            if (c[i][j] == 'J')
            {
                q.push({i, j});
                jul[i][j] = 1;
                OK = false;
            }
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0; k <= 7; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (c[x][y] == ' ' && jul[x][y] > 1 + jul[i][j])
            {
                jul[x][y] = 1 + jul[i][j];
                q.push({x, y});
            }
        }
    }
}
void Solve ()
{
    ofstream fout ("rj.out");
    short xf, yf, dmin, i, j;
    dmin = oo;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (rom[i][j] == jul[i][j] && rom[i][j] != oo)
                if (rom[i][j] < dmin)
                {
                    dmin = rom[i][j];
                    xf = i;
                    yf = j;
                }
        }
    fout << dmin << " " << xf << " " << yf << "\n";
    fout.close();
}
void Afisare()
{
    ofstream fout ("rj.out");
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            fout << rom[i][j] << " ";
        fout << "\n";
    }
    fout << "\n";
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            fout << jul[i][j] << " ";
        fout << "\n";
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
            fout << c[i][j];
        fout << "\n";
    }
}
int main()
{
    Read();
    Initiate();
    Board();
    LeeR();
    LeeJ();
    ///Afisare();
    Solve();
    return 0;
}