Cod sursa(job #2982659)

Utilizator lucaxsofLuca Sofronie lucaxsof Data 20 februarie 2023 18:02:42
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 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 lee(int nr)
{
	queue<pair<int, int>> v1;
	if (nr==0)
		v1.emplace(iR, jR);
	else
		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[nr][iv][jv]==0)
			{
				v1.emplace(iv, jv);
				pasi[nr][iv][jv] = pasi[nr][ii][jj] + 1;
			}
		}
	}
}

void b()
{
	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 ans = 99999989;

int main()
{
	read();
	b();
	pasi[0][iR][jR] = 1;
	pasi[1][iJ][jJ] = 1;
	lee(0);
	lee(1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (a[i][j]==' ' && pasi[0][i][j] == pasi[1][i][j] && pasi[0][i][j] != 0)
			{
				if (ans > pasi[0][i][j])
					iSol = i, jSol = j, ans = pasi[0][i][j];
			}
	cout << ans << ' ' << iSol << ' ' << jSol;
}