Cod sursa(job #2282475)

Utilizator dorufDoru Floare doruf Data 13 noiembrie 2018 19:52:03
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

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

const int Dim = 105, Inf = 0x3f3f3f3f;
const int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
const int dj[] = {0, 1, 0, -1, -1, 1, -1, 1};

struct Cel {
	int i, j;
};

char L[Dim][Dim];
int rc[Dim][Dim], jc[Dim][Dim];

int n, m, ip, jp ,is, js;
int soli, solj, tmin = Dim * Dim;
bool nw;

void ReadMatrix();
void LeeRomeo();
void LeeJulieta();
bool Ok(int i, int j);


int main()
{
	ReadMatrix();
	LeeRomeo();
	LeeJulieta();
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if((rc[i][j] == jc[i][j] && rc[soli][solj] > rc[i][j] && rc[i][j] != Inf) || (nw == false))
                 soli = i, solj = j, nw = true;
        }
    }
    fout << rc[soli][solj] + 1 << ' ' << soli << ' ' << solj << '\n';
    
}

void LeeRomeo()
{
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			rc[i][j] = Inf;

	queue<Cel> Q;
	rc[ip][jp] = 0;
	Q.push({ip, jp});

	int i, j, iv, jv;
	while (!Q.empty())
	{
		i = Q.front().i;
		j = Q.front().j;
		Q.pop();

		for (int d = 0; d < 8; ++d)
		{
			iv = i + di[d];
			jv = j + dj[d];
			if (Ok(iv, jv) && rc[iv][jv] > rc[i][j] + 1)
			{
				rc[iv][jv] = rc[i][j]  + 1;
				Q.push({iv, jv});
			}
		}
	}
}

void LeeJulieta()
{
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			jc[i][j] = Inf;

	queue<Cel> Q;
	jc[is][js] = 0;
	Q.push({is, js});

	int i, j, iv, jv;
	while (!Q.empty())
	{
		i = Q.front().i;
		j = Q.front().j;
		Q.pop();

		for (int d = 0; d < 8; ++d)
		{
			iv = i + di[d];
			jv = j + dj[d];
			if (Ok(iv, jv) && jc[iv][jv] > jc[i][j] + 1)
			{
				jc[iv][jv] = jc[i][j]  + 1;
				Q.push({iv, jv});
			}
		}
	}
}

bool Ok(int i, int j)
{
	if (i < 1 || i > n || j < 1 || j > m)
		return false;

	if (L[i][j] == 'X')
		return false;

	return true;
}

void ReadMatrix()
{
	fin >> n >> m;
	fin.get();
	for(int i = 1; i <= n; ++i)
    {
        fin.getline((L[i] + 1), Dim + 1);
        for(int j = 1; j <= m; ++j)
        {
            if(L[i][j] == 'R')ip = i, jp = j;
            if(L[i][j] == 'J')is = i, js = j;
        }

    }

}