Cod sursa(job #2183060)

Utilizator CatiCotorCotor Catinca CatiCotor Data 22 martie 2018 19:46:49
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

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

int r[101][101], ju[101][101];
int n , m;
char s[101];
const int di[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};
queue < pair<int, int> > q;
int ri, rj, ji, jj;

bool Ok(int i, int j, int a[101][101]);
void Lee(int i,int j, int a[101][101]);

int main()
{
    fin >> n >> m;
    fin.get();
    for (int i = 0; i < n; ++i)
    {
        fin.getline(s, 101);
        for (int j = 0; j < m; ++j)
        {
            if (s[j] == ' ')
                r[i][j] = ju[i][j] = -1;
            if ( s[j] == 'X')
                r[i][j] = ju[i][j] = -2;
            if ( s[j] == 'R')
                {
                ri = i;
                rj = j;
                }
            if (s[j] == 'J')
            {
                ji = i;
                jj = j;
            }
        }
    }

    Lee(ri, rj, r);
    Lee(ji, jj, ju);

    int imin, jmin, nrmin{10000};
    for (int i = 0; i < n; ++i )
        for (int j = 0; j < m; ++j)
    {
        if (r[i][j] == ju[i][j] && r[i][j] > 0 && r[i][j] < nrmin)
        {
            imin = i;
            jmin = j;
            nrmin = r[i][j];
        }
    }

    fout << nrmin << " " << imin + 1 << " " << jmin + 1;


}

void Lee(int i, int j, int a[101][101])
{
    a[i][j] = 1;
    q.push({i, j});
    while(!q.empty())
    {
        int lc = q.front().first;
        int cc = q.front().second;
        q.pop();

        for(int d = 0; d < 8; ++d)
        {
            int ln = lc + di[d];
            int cn = cc + dj[d];
            if ( Ok(ln, cn, a))
            {
                a[ln][cn] = a[lc][cc] + 1;
                q.push({ln, cn});
            }
        }
    }
}

bool Ok(int i, int j, int a[101][101])
{
    if (i < 0 || i > n || j < 0 || j > m)
        return false;
    if (a[i][j] != -1)
        return false;
    return true;
}