Cod sursa(job #2982593)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 20 februarie 2023 15:20:55
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 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 = 1e1;

int iR, iJ, jR, jJ;

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

int n, m;

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

char a[NMAX + 3][NMAX + 3];

void read()
{
	cin >> n >> m;
	cin.getline(a[0], NMAX + 2);
	for (int i = 1; i <= n; ++i)
		cin.getline((1 + a[i]), NMAX + 2);
	for (int i=1; i<=n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			if (a[i][j] == 'R')
				iR = i, jR = j;
			else if (a[i][j] == 'J')
				iJ = i, jJ = j;
		}
}

queue<pair<int, int>> v;

void solve()
{
	if ((iR == iJ) && (jR == jJ))
	{
		cout << 0 << ' ' << iR << ' ' << jJ;
		return;
	}

	v.emplace(iR, jR);
	v.emplace(iJ, jJ);

	pasi[0][iR][jR] = pasi[1][iJ][jJ] = 1;

	int nrQueue1 = 1, nrS1=0, nrQueue2 = 1, nrS2=0;

	int btimp=NMAX*NMAX, timp = 0;

	int ii, jj, iSol=NMAX, jSol=NMAX;

	while (!v.empty())
	{
		ii = v.front().first;
		jj = v.front().second;
		v.pop();

		timp++;

		//Romeo
		for (int i = 1; i <= nrQueue1; ++i)
		{
			for (int k = 0; k < 8; ++k)
			{
				int iv = ii + di[k];
				int jv = jj + dj[k];
				if (a[iv][jv] == ' ')
				{
					a[iv][jv] = 'R';
					pasi[0][iv][jv] = pasi[0][ii][jj] + 1;
					v.emplace(iv, jv);
					nrS1++;
				}
				else if (a[iv][jv] == 'J')
				{
					if (pasi[0][iv][jv] == pasi[1][iv][jv])
					{
						if (iv < iSol)
						{
							iSol = iv, jSol = jv;
						}
						else if (iv == iSol)
							if (jv < jSol)
								iSol = iv, jSol = jv;
					}
					else
					{
						a[iv][jv] = 'R';
						pasi[0][iv][jv] = pasi[0][ii][jj] + 1;
						v.emplace(iv, jv);
						nrS1++;
					}
				}
			}
		}
		nrQueue1 = nrS1;
		nrS1 = 0;

		for (int i = 1; i <= nrQueue2; ++i)
		{
			for (int k = 0; k < 8; ++k)
			{
				int iv = ii + di[k];
				int jv = jj + dj[k];
				if (a[iv][jv] == ' ')
				{
					a[iv][jv] = 'J';
					pasi[1][iv][jv] = pasi[1][ii][jj] + 1;
					v.emplace(iv, jv);
					nrS2++;
				}
				else if (a[iv][jv] == 'R')
				{
					if (pasi[1][iv][jv] == pasi[0][iv][jv])
					{
						if (iv < iSol)
						{
							iSol = iv, jSol = jv;
							btimp = timp;
						}
						else if (iv == iSol)
							if (jv < jSol)
								iSol = iv, jSol = jv, btimp=timp;
					}
					else
					{
						a[iv][jv] = 'J';
						pasi[1][iv][jv] = pasi[1][ii][jj] + 1;
						v.emplace(iv, jv);
						nrS2++;
					}
				}
			}
		}
		nrQueue2 = nrS2;
		nrS2 = 0;
	}
	cout << btimp << ' ' << iSol << ' ' << jSol;
}

int main()
{
	read();
	solve();
}