Cod sursa(job #2681272)

Utilizator andu9andu nita andu9 Data 5 decembrie 2020 11:03:35
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int rom[103][103], jul[103][103];
queue <int> lin, col;

int main()
{
    bool ok;
    char c;
    int n, i, m, j;
    int inci, incj, sfari, sfarj;
    int l1, c1, ln, cn;
    int minn, resi, resj;
    f >> n >> m;
    f.get (c);
    minn = 10003;
    for (i = 1; i <= n; i += 1)
    {
        ok = 0;
        for (j = 1; j <= m and !ok; j += 1)
        {
            f.get (c);
            if (c == 'R')
                inci = i, incj = j;
            else if (c == 'J')
                sfari = i, sfarj = j;
            else if (c == 'X')
                rom[i][j] = jul[i][j] = -1;
            if (c == '\n')
                ok = 1;
        }
        if (!ok)
            f.get (c);
    }
    for (i = 0; i <= n + 1; i += 1)
        rom[i][0] = rom[i][m + 1] = jul[i][0] = jul[i][m + 1] = -1;
    for (j = 0; j <= m + 1; j += 1)
        rom[0][j] = rom[n + 1][j] = jul[0][j] = jul[n + 1][j] = -1;
    lin.push (inci);
    col.push (incj);
    rom[inci][incj] = 1;
    while (!lin.empty ())
    {
        l1 = lin.front ();
        c1 = col.front ();
        for (i = 0; i <= 7; i += 1)
        {
            ln = l1 + dx[i];
            cn = c1 + dy[i];
            if (!rom[ln][cn])
            {
                lin.push (ln);
                col.push (cn);
                rom[ln][cn] = rom[l1][c1] + 1;
            }
        }
        lin.pop ();
        col.pop ();
    }
    lin.push (sfari);
    col.push (sfarj);
    jul[sfari][sfarj] = 1;
    while (!lin.empty ())
    {
        l1 = lin.front ();
        c1 = col.front ();
        for (i = 0; i <= 7; i += 1)
        {
            ln = l1 + dx[i];
            cn = c1 + dy[i];
            if (!jul[ln][cn])
            {
                lin.push (ln);
                col.push (cn);
                jul[ln][cn] = jul[l1][c1] + 1;
            }
        }
        lin.pop ();
        col.pop ();
    }
    for (i = 1; i <= n; i += 1)
    {
        for (j = 1; j <= m; j += 1)
        {
            if (rom[i][j] == jul[i][j] and rom[i][j] > 0)
            {
                if (rom[i][j] < minn)
                {
                    minn = rom[i][j];
                    resi = i;
                    resj = j;
                }
            }
        }
    }
    g << minn << ' ' << resi << ' ' << resj;
    return 0;
}