Cod sursa(job #2183214)

Utilizator muresanvladMuresan Vlad muresanvlad Data 22 martie 2018 22:18:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <cstring>
#include <queue>

std::ifstream in;
std::ofstream out;

int R[101][101], J[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};
std::queue < std::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()
{
    in.open("rj.in");
    in >> n >> m;
    in.get();
    for (int i = 0; i < n; ++i)
    {
        in.getline(s, 101);
        for (int j = 0; j < m; ++j)
        {
            if (s[j] == ' ')
                R[i][j] = J[i][j] = -1;
            if ( s[j] == 'X')
                R[i][j] = J[i][j] = -2;
            if ( s[j] == 'R')
            {
                ri = i;
                rj = j;
            }
            if (s[j] == 'J')
            {
                ji = i;
                jj = j;
            }
        }
    }

    in.close();

    Lee(ri, rj, R);
    Lee(ji, jj, J);

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

    out.open("rj.out");
    out << nrmin << " " << imin + 1 << " " << jmin + 1;
    out.close();

}

void Lee(int i, int j, int a[101][101])
{
    a[i][j] = 1;

    Q.push({i, j});
    while(!Q.empty())
    {
        int lin = Q.front().first;
        int col = Q.front().second;
        Q.pop();

        for(int d = 0; d < 8; ++d)
        {
            int next_line = lin + di[d];
            int next_column = col + dj[d];
            if ( Ok(next_line, next_column, a))
            {
                a[next_line][next_column] = a[lin][col] + 1;
                Q.push({next_line, next_column});
            }
        }
    }
}

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;
}