Матч 301, Убежать из тюрьмы (EscapingJail)

Дивизион 1, Уровень 2

В тюрьме заключенные перевязаны между собой цепями для того чтобы им было трудно убежать. Группа заключенных решилась бежать, и ей надо выбрать двух, которые одновременно смогут нажать на две кнопки, находящиеся на некотором расстоянии.

В массиве chain описывается конфигурация соединений цепями заключенных. Значение chain[i][j] характеризует расстоянию между i -ым и j - ым заключенным. Если оно равно:

‘0’ – ‘9’, то расстояние равно соответственно значению от 0 до 9 футов.

‘a’ – ‘z’, то расстояние равно соответственно значению от 10 до 35 футов.

‘A’ – ‘Z’, то расстояние равно соответственно значению от 36 до 61 футов.

‘ ‘ (пробел): между заключенными нет цепи.

Необходимо найти наибольшее расстояние, которое могут обеспечить двое заключенных. Если они могут нажать на две кнопки, находящиеся на любом расстоянии, то вернуть -1.

Класс: EscapingJail

Метод: int getMaxDistance(vector<string> chain)

Ограничения: chain содержит от 2 до 50 элементов, chain[i] содержит n символов, где n – количество элементов chain, chain[i][j] = chain[j][i], chain[i][j] содержит один из символов ‘0’ – ‘9’, ‘a’ – ‘z’, ‘A’ – ‘Z’.

Вход. Массив строк chain, описывающий конфигурацию соединений цепями заключенных.

Выход. Наибольшее расстояние между кнопками, при котором найдутся двое заключенных, которые смогут их нажать. Если заключенные могут нажать на две кнопки, находящиеся на любом расстоянии, то вернуть -1.

Пример входа

chain

{"0568",
"5094",
"6903",

"8430"}

{"0 ",

" 0"}

{"0AxHH190",
"A00f3AAA",
"x00 ",
"Hf 0 x ",
"H3 0 ",
"1A 0 ",
"9A x 0Z",

"0A Z0"}

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

8

-1

43

РЕШЕНИЕ

алгоритм Флойда - Уоршела

По массиву chain строим матрицу смежности m, где m[i][j] содержит длину цепи между i -ым и j - ым заключенным. Если цепи между ними нет, установим m[i][j] = INF = 1000000000. Запускаем алгоритм Флойда – Уоршела поиска всех кратчайших путей между парами вершин. Затем ищем наибольшее расстояние между вершинами – диаметр графа, который и возвращаем. Если он равен бесконечности (INF), то возвращаем -1.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#define INF 1000000000

using namespace std;

int m[50][50],i,j,k,n,res;

int convert(char n)

{

if (n == ' ') return INF;

if (n <= '9') return n - '0';

if (n <= 'Z') return n - 'A' + 36;

return n - 'a' + 10;

}

class EscapingJail

{

public:

int getMaxDistance(vector<string> chain)

{

n = chain.size();

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

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

m[i][j] = convert(chain[i][j]);

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]) m[i][j] = m[i][k] + m[k][j];

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

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

if (m[i][j] > res) res = m[i][j];

return (res == INF) ? -1 : res;

}

};