Playing poohsticks in the Styx

Когда деревья были большими, а память в компьютерах - маленькой, дети развлекались написанием программ на языке BASIC. Язык был простой и незамысловатый, но с появлением пиксельной графики на микрокомпьютерах и, соответственно, операторов отрисовки точек, отрезков и дуг окружностей или эллипсов, какая-то добрая душа добавила в язык и оператор закраски замкнутой области (PAINT или FILL).

Ну а что ж, надо же как-то удобно рисовать закрашенные кружочки и многоугольнички?

Одни разработчики были умные. Они решили сделать так: перед рисованием контура фигуры программист должен сказать "приготовься закрашивать то, что я сейчас буду рисовать", а после окончания рисования контура - "давай закрашивай". Фигура при этом должна быть "выпуклая по горизонтали", т.е. пересечение любой горизонтальной прямой и контура должно быть не более чем две точки или отрезка (а если кто не читает инструкции, тот ССЗБ). Процедура закраски должна всего лишь запоминать, какие были самая левая и самая правая точки контура в каждой строке экрана, и по заключительной команде закрасить всё между ними.
Алгоритм простой, памяти много не требует, но рисовать таким образом, например, кремлевскую стену довольно утомительно.

Другие разработчики были хитрые. Они решили сделать так: операция закраски будет пытаться красить любые фигуры, пользуясь стеком или очередью для запоминания, в какие закоулки нужно не забыть зайти, а если фигура окажется слишком сложная, и алгоритму потребуется больше временной памяти, чем есть, то программа или вылетит по ошибке нехватки памяти (если основное качество разработчика было laziness), или фигура не докрасится до конца (если основное качество разработчика было impatience) или машина зависнет/рестартует (если основное качество разработчика было hubris).
Алгоритм простой, быстрый, но перекрашивать таким образом, например, случайно сгенерированный лабиринт довольно рискованно.

Третьи разработчики были добрые. Они решили сделать так: операция закраски будет пытаться красить любые фигуры, пользуясь фиксированным количеством памяти, а если фигура окажется слишком сложная, то нефиг было программисту выпендриваться — подождёт.
Алгоритм совершенно бешеный, и описание на естественном языке, и псевдокод; и на многосвязных фигурах медленный, как моя жизнь. Курсор бегает по лабиринту кругами, как крыса, а толку через час по чайной ложке (скажем, для закраски квадрата 50х50 с 13% случайно расставленных точек может потребоваться больше 100 тысяч шагов).
В псевдокоде особенно восхищает вот это:

cur, mark, and mark2 each hold either pixel coordinates or a null value
         NOTE: when mark is set to null, do not erase its previous coordinate value.
               Keep those coordinates available to be recalled if necessary.

(Поняли теперь, как nullable references должны быть устроены?)

Самое смешное, что алгоритм всё же действительно работает.