Cod sursa(job #2423659)

Utilizator cristiangeambasuCristian Geambasu cristiangeambasu Data 21 mai 2019 20:14:33
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <queue>

int** BFS(int** mat, int n, int m, int x, int y)
{
	int** dist = new int* [n];
	for(int i = 0; i < m; i++)
	{
		dist[i] = new int[m];
		std::fill_n(dist[i], m, -1);
	}

	std::queue<int> queue;
	queue.push(y * m + x);
	dist[y][x] = 1;

	while(!queue.empty())
	{
		int x = queue.front();
		int u = x / m;
		int v = x % m;

		for(int r = -1; r <= 1; r++)
		{
			if(u + r < 0 || u + r >= n)
				continue;

			for(int c = -1; c <= 1; c++)
			{
				if((c == 0 && r == 0) || v + c < 0 || v + c >= m)
					continue;

				if(dist[u + r][v + c] < 0 && mat[u + r][v + c])
				{
					dist[u + r][v + c] = dist[u][v] + 1;
					queue.push((u + r) * m + (v + c));
				}
			}
		}

		queue.pop();
	}

	return dist;
}

void main()
{
	std::ifstream fin("rj.in");
	std::ofstream fout("rj.out");
	if(!fin.is_open() || !fout.is_open())
		return;

	int n = 0, m = 0, r_x = 0, r_y = 0, j_x = 0, j_y = 0;
	char ch = 0;
	int** mat = nullptr;
	int** dist_rom = nullptr;
	int** dist_jul = nullptr;

	fin >> n >> m;
	fin >> std::noskipws >> ch;

	mat = new int* [n];
	for(int i = 0; i < n; i++)
	{
		mat[i] = new int[m];
		for(int j = 0; j < m; j++)
		{
			fin >> std::noskipws >> ch;
			switch(ch)
			{
			case 'R':
				mat[i][j] = 1;
				r_x = j;
				r_y = i;
				break;
			case 'J':
				mat[i][j] = 1;
				j_x = j;
				j_y = i;
				break;
			case 'X':
				mat[i][j] = 0;
				break;
			default:
				mat[i][j] = 1;
				break;
			}
		}

		fin >> std::noskipws >> ch;
	}

	dist_rom = BFS(mat, n, m, r_x, r_y);
	dist_jul = BFS(mat, n, m, j_x, j_y);

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(dist_rom[i][j] > 0 && dist_rom[i][j] == dist_jul[i][j])
			{
				fout << dist_rom[i][j] << ' ' << i + 1 << ' ' << j + 1;
				i = n;
				j = m;
			}
		}
	}

	for(int i = 0; i < n; i++)
	{
		delete[] mat[i];
		delete[] dist_rom[i];
		delete[] dist_jul[i];
	}

	delete[] mat;
	delete[] dist_rom;
	delete[] dist_jul;
}