Cod sursa(job #2982626)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 20 februarie 2023 16:31:35
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 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 = 1e2;

int iSol = NMAX, jSol = NMAX, t;
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;
		}
}

void lee1()
{
	pasi[0][iR][jR] = 1;
	pasi[1][iJ][jJ] = 1;
	queue<pair<int, int>> v1;
	v1.emplace(iR, jR);
	int ii, jj;
	while (!v1.empty())
	{
		ii = v1.front().first;
		jj = v1.front().second;
		v1.pop();

		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';
				v1.emplace(iv, jv);
				pasi[0][iv][jv] = pasi[0][ii][jj] + 1;
			}
		}
	}
}


void lee2()
{
	queue<pair<int, int>> v;
	v.emplace(iJ, jJ);
	int ii, jj;
	while (!v.empty())
	{
		ii = v.front().first;
		jj = v.front().second;
		v.pop();

		for (int k = 0; k < 8; ++k)
		{
			int iv = ii + di[k];
			int jv = jj + dj[k];

			if (a[iv][jv] == 'R')
			{
				pasi[1][iv][jv] = pasi[1][ii][jj] + 1;
				if (pasi[1][iv][jv] == pasi[0][iv][jv])
				{
					a[0][0] = '.';
					if ((iv < iSol) || (iv == iSol && jv < jSol))
					{
						iSol = iv; jSol = jv; t = pasi[0][iv][jv];
					}
				}
				v.emplace(iv, jv);
				a[iv][jv] = 'J';
			}
		}
	}
	cout << t << ' ' << iSol << ' ' << jSol;
}

int main()
{
	read();
	lee1();
	lee2();
}