Cod sursa(job #2982652)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 20 februarie 2023 17:38:10
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 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;

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

void lee2()
{
	pasi[1][iJ][jJ] = 1;
	queue<pair<int, int>> v1;
	v1.emplace(iJ, jJ);
	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] == ' ' && pasi[1][iv][jv]==0)
			{
				v1.emplace(iv, jv);
				pasi[1][iv][jv] = pasi[1][ii][jj] + 1;
			}
		}
	}
}

int main()
{
	read();
	if (iR == iJ and jR == jJ)
	{
		cout << 0 << ' ' << iR << ' ' << jJ;
		return 0;
	}
	lee1();
	lee2();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (pasi[0][i][j] == pasi[1][i][j] && pasi[0][i][j]!=0)
			{
				cout << pasi[0][i][j] << ' ' << i << ' ' << j;
				return 0;
			}
}