Матч 39, Линейный город (LinearCity)

В линейном городе все дома расположены на прямой, и люди знают только свое относительное местоположение относительно друг друга. Информация о домах задана в строке refSource и массивах source и destination: i - ый элемент refSource указывает на направление, в котором требуется идти чтобы попасть из дома source[i] в дом destination[i]. Города пронумерованы числами от 0 до n – 1 (здесь n равно числу домов в городе).

Приезжий хочет установить относительное расположение некоторых пар домов. У него имеются массивы чисел source и destination. Для каждого значения i (0 £ i £ k – 1, k – длина массива source) необходимо установить, справа или слева от source[i] находится destination[i]. Соответственно вернуть следует слово “LEFT” или “RIGHT”. Если их относительного положения установить невозможно, то вернуть “UNKNOWN”.

Класс: LinearCity

Метод: vector<string> getReference(vector<int> refSource,

vector<int> refDestination,

string refDirection, int n,

vector<int> source, vector<int> destination)

Ограничения: refSource содержит от 1 до 50 элементов, 0 £ refSource[i], refDestination[i], source[i], destination[i] £ n – 1, refSource[i] ¹ refDestination[i] для каждого 0 £ i £ m – 1 (m – длина массива refSource), каждый символ refDirection равен ‘L’ или ‘R’, 2 £ n £ 50, source[i] ¹ destination[i] для каждого 0 £ i £ k - 1 (k – длина массива source).

Вход. Строка refSource и массивы source и destination, задающие информацию об относительном расположении некоторых пар городов, число городов n, массивы source и destination, содержащие запросы к городу.

Выход. Массив строк, i - ый элемент которого равен “LEFT”, “RIGHT” или “UNKNOWN” в зависимости от взаимного расположения городов source[i] и destination[i].

Пример входа

refSource	refDestination	refDirection	n	source	destination
{1, 2}	{2, 0}	“RR”	3	{1, 0}	{0, 1}
{1, 0}	{2, 2}	“RL”	3	{1, 0}	{0, 1}
{2, 3, 1, 0, 2, 0, 5, 5}	{1, 4, 4, 4, 4, 3, 2, 3}	"RLRLRLLL"	6	{0, 1, 0}	{2, 3, 5}

Пример выхода

{"RIGHT", "LEFT"}

{"RIGHT", "LEFT"}

{"LEFT", "RIGHT", "UNKNOWN"}

РЕШЕНИЕ

транзитивное замыкание

Заведем двумерный массив m, в котором установим m[i][j] = 1, если по условию задачи i - ый город расположен левее j - ого. Иначе положим m[i][j] = 0. Если refDirection[i] = 'R', то устанавливаем m[refSource[i]][refDestination[i]] = 1, иначе город refDestination[i] находится левее refSource[i], поэтому устанавливаем m[refDestination[i]][refSource[i]] = 1.

Запустим алгоритм транзитивного замыкания на графе, матрица смежности которого находится в матрице m. Теперь m[i][j] = 1, если мы точно можем установить, что i - ый город расположен левее j - ого. То есть если m[source[i]][destination[i]] = 1, то выводим “RIGHT”. Если m[destination[i]][source[i]] = 1, то выводим “LEFT”. Если m[source[i]][destination[i]] = 0, то ничего установить про относительное расположение городов с номерами destination[i] и source[i] нельзя, поэтому возвращаем "UNKNOWN".

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

int m[50][50];

class LinearCity

{

public:

vector<string> getReference(vector<int> refSource,

vector<int> refDestination,

string refDirection, int n,

vector<int> source, vector<int> destination)

{

int i, j, k;

vector<string> res;

memset(m,0,sizeof(m));

for(i = 0; i < refSource.size(); i++)

if (refDirection[i] == 'R')

m[refSource[i]][refDestination[i]] = 1;

else m[refDestination[i]][refSource[i]] = 1;

for(k = 0; k < n; k++)

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

if (m[i][k] && m[k][j]) m[i][j] = 1;

for(i = 0; i < source.size(); i++)

{

if (m[source[i]][destination[i]] == 1) res.push_back("RIGHT"); else

if (m[destination[i]][source[i]] == 1) res.push_back("LEFT"); else

res.push_back("UNKNOWN");

}

return res;

}

};