Сразу примечение: я знаю, что она не идентична классической "о назначениях", просто не придумал о чём же она, кроме как о назначениях. Помогите пожалста либо доказать, что жадный подход нормально работает, либо свести задачу к какой-нибудь известной.

Суть вот в чём: есть разноцветные ленточки единичной ширины, их можно переплетать, получая прямоугольный рисунок. Если в некой клетке одна из лент A идёт поверх ей перпендикулярной B, то цвет у клетки, соответствующей пересечению, будет цветом ленты A. Если же A подныривает под B, то значит цвет у клетки будет цветом ленты B.

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

Ограничения по ширине и высоте ~1500x1500, ограничение по числу цветов ~40, по времени что-нибудь человекоразумное.

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

Если в какой-то момент очереди обработки опустели, значит задача слегка редуцировалась. Например имеем такой вот инпут:

   ???????
 
?  AAAAAAB
?  DXXXXXB
?  DXYYYXB
?  DCCCCCC
?  DXXXXXB
?  DEEEEEE

Предполагаем, что 'A' в левом вехрнем углу задаёт цвет первой горизонтальной ленты. Тогда 'B' в последнем столбце должна задать цвет последней, седьмой, вертикальной ленты. Обрабатывая эту вертикальную ленту, в четвёртой строке натолкнёмся на 'C' - значит это цвет четвёртой горизонтальной ленты, и 'E' в последней, шестой, строке, значит это цвет последней горизонтальной ленты. Обрабатывая горизонтальные ленты 4 и 6 в любом порядке выясним, что у первого столбца должен быть цвет 'D'. Обрабатывая первый столбец ничего уже полезного не выясним - в первой строке цвет был 'A', но это мы и раньше уже знали.

Задача слегка редуцировалась:

   D?????B
                  ?????
A  AAAAAAB
?  DXXXXXB     ?  XXXXX
?  DXYYYXB  => ?  XYYYX
C  DCCCCCC     ?  XXXXX
?  DXXXXXB
E  DEEEEEE

Если она не редуцировалась, значит где-то упёрлись в противоречие, стоит вернуться в начало и попробовать связать 'A' не со строкой, а со столбцом. Если и этот вариант не сработал, то сразу же печать ругательного сообщения и завершение процесса.

Такой вот приблизительно подход приходит на ум сразу, но не получается доказать, что он всегда будет находить вариант сопоставления корректной картинке каких нибудь цветов для лент. Поскольку после редукции алгоритм уже не возвращается назад, значит гипотетически возможна такая ситуация, когда неверно выбранное направление на шаге 1 через несколько редукций заведёт в тупик. Возможно ли придумать контрпример, на котором алгоритм сфэйлит?

PS: возможно, что неправильный, имплементэйшн тут. http://codepaste.net/ob8imc