Cod sursa(job #2979309)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 14 februarie 2023 21:50:20
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <math.h>
#include <vector>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <bitset>
#include <string>
//#include <bits/stdc++.h>
using namespace std;

ifstream cin("rj.in");
ofstream cout("rj.out");	

const int NMAX = 130;

char a[NMAX + 1][NMAX + 1];

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

int n, m, iR, jR, iJ, jJ;

void read()
{
	cin >> n >> m;
	cin.getline((1+a[1]), 256);
	for (int i = 1; i <= n; i++)
		cin.getline((1+a[i]), 256);

	int ok1 = 1, ok2 = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; ++j)
		{
			if (a[i][j] == 'J')
			{
				ok1 = 0;
				iJ = i;
				jJ = j;
			}
			else if (a[i][j] == 'R')
			{
				iR = i;
				ok2 = 0;
				jR = j;
			}
			if (!ok1 && !ok2)
				return;
		}
}

void bordare()
{
	for (int i = 0; i <= n; i++)
		a[i][0] = a[i][m + 1] = 'X';
	for (int j = 0; j <= m; ++j)
		a[0][j] = a[n + 1][j] = 'X';
}

int pasi[2][NMAX + 1][NMAX + 1];

void lee()
{
	if (iJ == iR and jR == jJ)
	{
		cout << 0 << ' ' << jJ << ' ' << iJ;
		return;
	}
	int nrJ=1, nrR=1, timp=1;
	int nrQueue1, nrQueue2;
	int done = 0, i_min = 101, j_min = 101;

	queue<pair<int, int>> vR;
	queue<pair<int, int>> vJ;
	
	int ii1 = iR, jj1 = jR, ii2 = iJ, jj2 = jJ;
	
	pasi[0][ii1][jj1] = pasi[1][ii2][jj2] = 1;

	vR.emplace(ii1, jj1);
	vJ.emplace(ii2, jj2);
	while (!vJ.empty() && !vR.empty())
	{
		timp++;
		nrQueue1 = 0;
		for (int nr = 1; nr <= nrR; ++nr)
		{
			ii1 = vR.front().first;
			jj1 = vR.front().second;
			vR.pop();
			for (int k = 0; k < 8; k++)
			{
				int iv = ii1 + di[k], jv = jj1 + dj[k];
				if (a[iv][jv] == ' ')
				{
					a[iv][jv] = 'R';
					pasi[0][iv][jv] = timp;
					vR.emplace(iv, jv);
					nrQueue1++;
				}
				if (a[iv][jv] == 'J')
				{
					pasi[0][iv][jv] = timp;
					if (pasi[1][iv][jv] == pasi[0][iv][jv])
					{
						if (iv < i_min)
							i_min = iv, j_min = jv;
						else if (iv == i_min && jv < j_min)
							i_min = iv, j_min = jv;
					}
				}
			}
		}
		nrR = nrQueue1;


		nrQueue2 = 0;
		for (int nr = 1; nr <= nrJ; ++nr)
		{
			ii2 = vJ.front().first;
			jj2 = vJ.front().second;
			vJ.pop();
			for (int k = 0; k < 8; k++)
			{
				int iv = ii2 + di[k], jv = jj2 + dj[k];
				if (a[iv][jv] == ' ')
				{
					a[iv][jv] = 'J';
					vJ.emplace(iv, jv);
					pasi[1][iv][jv] = timp;
					nrQueue2++;
				}
				if (a[iv][jv] == 'R')
				{
					pasi[1][iv][jv] = timp;
					if (pasi[1][iv][jv] == pasi[0][iv][jv])
					{
						if (iv < i_min)
							i_min = iv, j_min = jv;
						else if (iv == i_min && jv < j_min)
							i_min = iv, j_min = jv;
					}

				}
			}
		}
		nrJ = nrQueue2;
	}
	cout << pasi[0][i_min][j_min];
	cout << ' ' << i_min << ' ' << j_min;
}


int main()
{
	read();
	bordare();
	lee();
}