Регистрация
Войти
Стать экспертом Правила
Информатика

Дано растровое изображение в 24-х битной цветовой модели RGB, разбитое на 16 квадратов, каждый из которых залит одним цветом. Каждый квадрат обозначен латинской буквой, как показано на рисунке справа.Исходное изображениеЦвета квадратов приведены в таблице:R G BA 0 190 160B 0 165 160C 0 140 185D 0 150 170E 0 140 160F 0 120 130G 0 140 110H 0 130 170I 0 120 190J 0 90 160K 0 115 160L 0 140 130M 0 160 190N 0 140 145O 0 140 210P 0 160 130Цветовая модель RGB может быть представлена в виде трехмерного пространства с прямоугольной системой координат и осями R, G и B соответственно. Тогда цвет любого пикселя может быть определен как точкав этом трехмерном пространстве.Инструмент «волшебная палочка» в большинстве графических редакторов работает следующим образом. У инструмента есть один параметр T – чувствительность. Пользователь применяет инструмент к одному из пикселей изображения – исходному пикселю. Считываются цветовые координаты исходного пикселя (значения R, G и B для цвета этого пикселя) и тем самым определяется точка в пространстве RGB. Строится шар радиусом T с центром в этой точке. Затем выделяются все пиксели изображения, для которых выполняется следующая пара условий:1. Точка в пространстве RGB, соответствующая цвету этого пикселя, находится внутри или на границе построенного шара.2. Между этим пикселем и исходным пикселем можно построить путь, проходящий через смежные (имеющие общую границу) пиксели, для которых точки пространства RGB также находятся внутри или на границе построенного шара.Определите минимальное значение параметра T, такое, что существует хотя бы один пиксель на исходном изображении, применение к которому инструмента «волшебная палочка» приведёт к выделению всех пикселей этого изображения. В ответе укажите через пробел сначала латинскую букву, обозначающую квадрат, содержащий этот пиксель к которому нужно применить инструмент, а затем целое число - найденное минимальное значение T.Примечание. В задании описано стандартное поведение инструмента «Волшебная палочка» без опций сглаживания и других дополнительных опций.

ОТВЕТЫ
Если надо, чтобы выделились все пиксели, T должно быть не меньше, чем расстояние от исходной точки до самой дальней (в пространстве RGB). При этом расположение ячеек не играет роли. Остается перебрать все варианты начальных точек, для каждого найти наименьшее Т, и из полученных значений выбрать минимальное.

Код (python 3.5):
from math import sqrt, ceil
points = [["A",0,190,160],["B",0,165,160],["C",0,140,185],["D",0,150,170],
          ["E",0,140,160],["F",0,120,130],["G",0,140,110],["H",0,130,170],
          ["I",0,120,190],["J",0,90,160],["K",0,115,160],["L",0,140,130],
          ["M",0,160,190],["N",0,140,145],["O",0,140,210],["P",0,160,130]]
minT2 = 3*256**2
minpt = "A"
for pt in points:
    T2 = 0
    for pt2 in points:
        T2 = max(T2, (pt[1]-pt2[1])**2+(pt[2]-pt2[2])**2+(pt[3]-pt2[3])**2)
    if T2 < minT2:
        minpt, minT2 = pt[0], T2
print(minpt, ceil(sqrt(T2)))
853
Контакты
Реклама на сайте
Спрошу
О проекте
Новым пользователям
Новым экспертам