Дано растровое изображение в 24-х битной цветовой модели RGB, разбитое ** 16 квадратов,...

Question

78 просмотров

Дано растровое изображение в 24-х битной цветовой модели RGB, разбитое на 16 квадратов, каждый из которых залит одним цветом. Каждый квадрат обозначен латинской буквой, как показано на рисунке справа.
Исходное изображение

Цвета квадратов приведены в таблице:
R G B
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

Цветовая модель RGB может быть представлена в виде трехмерного пространства с прямоугольной системой координат и осями R, G и B соответственно. Тогда цвет любого пикселя может быть определен как точка в этом трехмерном пространстве.
Инструмент «волшебная палочка» в большинстве графических редакторов работает следующим образом. У инструмента есть один параметр T – чувствительность. Пользователь применяет инструмент к одному из пикселей изображения – исходному пикселю. Считываются цветовые координаты исходного пикселя (значения R, G и B для цвета этого пикселя) и тем самым определяется точка в пространстве RGB. Строится шар радиусом T с центром в этой точке. Затем выделяются все пиксели изображения, для которых выполняется следующая пара условий:
1. Точка в пространстве RGB, соответствующая цвету этого пикселя, находится внутри или на границе построенного шара.
2. Между этим пикселем и исходным пикселем можно построить путь, проходящий через смежные (имеющие общую границу) пиксели, для которых точки пространства RGB также находятся внутри или на границе построенного шара.
Определите минимальное значение параметра T, такое, что существует хотя бы один пиксель на исходном изображении, применение к которому инструмента «волшебная палочка» приведёт к выделению всех пикселей этого изображения. В ответе укажите через пробел сначала латинскую букву, обозначающую квадрат, содержащий этот пиксель к которому нужно применить инструмент, а затем целое число - найденное минимальное значение T.
Примечание. В задании описано стандартное поведение инструмента «Волшебная палочка» без опций сглаживания и других дополнительных опций.

Информатика Fovden_zn (76 баллов) 11 Май, 18 | 78 просмотров

Дан 1 ответ

Правильный ответ

Если надо, чтобы выделились все пиксели, 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)))

nelle987_zn (148k баллов) 11 Май, 18