Cod sursa(job #3185247)

Utilizator PetraPetra Hedesiu Petra Data 18 decembrie 2023 16:52:02
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

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

int n, m, i1, j1, i2, j2, mn = 0x3f, i_min, j_min, a[101][101], viz[101][101][2],
d[8][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
struct coord {
    int r, j;
};
coord val[101][101][2];
struct q_entry {
    int i, j, index, bit;
};
queue<q_entry> q;

int on_map(int i, int j)
{
    return (1 <= i && i <= n && 1 <= j && j <= m);
}
void lee(int istart, int jstart, char ch, bool bit)
{
    memset(viz, 0, sizeof(viz));
    if (ch == 'R') val[istart][jstart][bit].r = 1;
    if (ch == 'J') val[istart][jstart][bit].j = 1;
    viz[istart][jstart][bit] = 1;

    q.push({istart, jstart, 2, !bit});
    while (!q.empty())
    {
        q_entry c = q.front();
        q.pop();
        for (int k = 0; k < 8; k++)
        {
            int xx = c.i + d[k][0], yy = c.j + d[k][1];
            if (!on_map(xx, yy)) continue;
            if (a[xx][yy] == 1) continue;
            if (viz[xx][yy][c.bit]) continue;

            viz[xx][yy][c.bit] = 1;
            if (ch == 'R') val[xx][yy][c.bit].r = c.index;
            if (ch == 'J') val[xx][yy][c.bit].j = c.index;

            q.push({xx, yy, c.index + 1, !c.bit});
        }
    }
}


int main()
{
    fin >> n >> m;
    fin.get();
    for (int i = 1; i <= n; i++)
    {
        char c[102];
        fin.getline(c, 101);
        for (int j = 0; j < m; j++)
        {
            if (c[j] == 'X') a[i][j+1] = 1;
            else if (c[j] == 'R') {
                a[i][j+1] = 1;
                i1 = i; j1 = j+1;
            }
            else if (c[j] == 'J') {
                a[i][j+1] = 1;
                i2 = i; j2 = j+1;
            }
        }
    }
    lee(i1, j1, 'R', 0);
    lee(i2, j2, 'J', 0);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (val[i][j][0].r != 0 && val[i][j][0].j != 0)
            {
                if (mn > max(val[i][j][0].r, val[i][j][0].j))
                {
                    mn =  max(val[i][j][0].r, val[i][j][0].j);
                    i_min = i;
                    j_min = j;
                }
            }
            if (val[i][j][1].r != 0 && val[i][j][1].j != 0)
            {
                if (mn > max(val[i][j][1].r, val[i][j][1].j))
                {
                    mn = max(val[i][j][1].r, val[i][j][1].j);
                    i_min = i;
                    j_min = j;
                }
            }

        }
    }
    fout << mn << " " << i_min << " " << j_min;
    return 0;
}