Cod sursa(job #2979279)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 14 februarie 2023 21:19:53
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#define _CRT_SECURE_NO_WARNINGS

#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 aa[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(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';
}

bool w[NMAX + 1][NMAX+1];

void lee()
{
	if (iJ == iR and jR == jJ)
	{
		cout << iJ << ' ' << jJ << ' ' << 0;
		return;
	}
	int ansi, ansj, timp=1, tJ=0, tR=0, nrJ=1, nrR=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;
	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';
					vR.emplace(iv, jv);
					nrQueue1++;
				}
				if (a[iv][jv] == 'J')
				{
					done = 1;
					//cout << timp << ' ' << 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;
		if (nrR != 0)
			timp++;


		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);
					nrQueue2++;
				}
				if (a[iv][jv] == 'R')
				{
					done = 1;
					//cout << timp << ' ' << 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;
		if (done)
		{
			cout << timp << ' ' << i_min << ' ' << j_min << ' ';
			return;
		}
	}
}


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