Автор: С.В.Шедов

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

Наш сканер является полностью задокументированным устройством, кроме того, каждое представление позволяет однозначно восстановить таблицу. Саму таблицу мы хранить в памяти не будем – памяти просто не хватит. Можно было бы организовать побитовое хранение матрицы, но это сопряжено с техническими проблемами, которых мы постараемся избежать при помощи эффективного алгоритма. Будем получать таблицу последовательно по строкам, считая по ходу количество белых клеток. Еще раз подчеркнем, что саму таблицу мы в памяти хранить не будем.

Сначала решим упрощенную задачу. Допустим, что у нас не бывает вертикальных полос, а есть только горизонтальные. Рассмотрим решение на примере. Пусть дан фрагмент исходной таблицы:

I\j	1	2	3	4	5	6	7	8	9	10	11	12
1
2

Она кодируется следующими пятью горизонтальными полосами:

1 полоса: 1 5 4 – начальная клетка полосы (1,5), ее длина равна 4.

2 полоса: 1 7 3

3 полоса: 2 2 2

4 полоса: 2 7 5

5 полоса: 2 11 1

Расставим в таблице цифры, соответствующе полосам, которые описывают данную клетку.

I\j	1	2	3	4	5	6	7	8	9	10	11	12
1					1	1	1,2	1,2	2
2		3	3				4	4	4	4	4,5

Как видим, некоторые клетки могут описываться сразу несколькими полосами. Считываем из файла самую первую полосу и храним ее в переменных newi, newj и d – начальная клетка полосы и ее длина. Затем идем по матрице до тех пор, пока текущая клетка не станет равна начальной клетке первой полосы. Очевидно, что все пройденные до этого момента клетки – белые. Не забываем считать их.

Для нашего примера мы пройдем четыре белые клетки, пока не поравняемся с первой полосой. (i=1, j=5, d=4). Теперь обрабатываем полосу, в которую мы пришли. В переменной maxj будем хранить столбец, где кончается первая полоса. Очевидно, что maxj=j+d-1=5+4-1=8.

Таким образом, при дальнейшем проходе по первой строке, если номер столбца j будет меньше, чем maxj, то текущая клетка – черная, поскольку на ней лежит первая полоса.

На этом можно считать обработку первой полосы законченной. Поскольку эта полоса нам больше не понадобится, то считываем в переменные newi, newj и d следующую полосу. Так как по условию в каждой клетке начинается не более одной полосы, то обработку новой полосы мы проведем позже: когда придем в клетку, где она начинается. Обратите внимание, что в нашем алгоритме мы пользуемся тем фактом, что полосы в исходном файле задаются по строкам слева направо, иначе бы данный алгоритм был совершенно неприменим!

Дальше мы пройдем две черные клетки (1,5) и (1,6), пока не поравняемся с началом второй полосы. i=1, j=7, d=3. Обрабатываем вторую полосу, то есть определим где она кончается. maxj=j+d-1=7+3-1=9. Указатель maxj сейчас указывает на столбец 8, а новая полоса заканчивается в 9 столбце, значит, указатель нужно передвинуть на 9, так как новая полоса простирается дальше прежней.

Такую проверку необходимо вставить в нашу программу:

if maxj < j+d-1 then

maxj := j+d-1;

Таким образом, мы подсчитываем белые клетки тогда, когда текущий столбец j не покрывается никакой горизонтальной полосой, то есть j > maxj. Для первой строки мы найдем 7 белых клеток. А что необходимо сделать при переходе на новую строку? Разумеется – обнулить указатель maxj. Он был актуален только для предыдущей строки, а на новой строке будут уже новые полосы.

Теперь переходим к обработке второй строки. Как только мы поравняемся с началом очередной полосы, то указатель maxj сместится на столбец 3, и пока j не превысит это значение, белые клетки считаться не будут. Затем мы пройдем три белые клетки и дойдем до четвертой полосы и здесь опять указатель изменит свое значение. В отличие от предыдущей строки, он не удлиняет текущую полосу, а указывает на конец новой полосы, но сути дела это не меняет.

Обратите внимание, что когда мы дойдем до пятой полосы, то указатель maxj обновлен не будет, так как пятая полоса заканчивается одновременно с четвертой.

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

Рассмотрим пример:

i\j	1	2	3	4	5	6
1		1			2	2
2		1
3		1,3		4		5
4		3		4

Полосы 1, 3 и 4 – вертикальные, 2 и 5 – горизонтальные (для полосы в одну клетку на самом деле это не существенно). Когда мы будем обрабатывать вторую строку, то последней считанной полосой будет вторая, и мы уже не будем «помнить» информацию о первой полосе. Тем не менее, первая полоса дает на второй строке одну черную клетку и мы должны ее учесть.

Для этого заведем массив X из N элементов, где в X[j] записываем в какой строке заканчивается максимальная из просмотренных ранее вертикальных полос j-го столбца. Очевидно, что в процессе работы программы элементы этого массива могут изменяться. Например, после обработки первой полосы X[2]=3, а после обработки третьей значение X[2] будет изменено на 4. В четвертом столбце у нас только одна вертикальная полоса, значение X[4]=4 изменено не будет.

Таким образом, если i<=x[j], то текущая клетка покрывается какой-то вертикальной полосой, рассмотренной ранее. Изменим проверку того, является ли текущая клетка белой:

if (i > x[j]) and (j > maxj) then inc(counter);

Перейдем к решению второго пункта задачи. Мы произвели перевод данных из внутреннего формата сканера в таблицу, но саму таблицу, как уже отмечалось выше, в памяти мы хранить не можем. Поэтому необходимо подсчитывать число фигур «на лету», имея в распоряжении одну или несколько строк. Можно применить один из известных алгоритмов послойного связывания, но наряду со сложностями в реализации он обладает недостатком – низкой производительностью на примерах, где области постоянно приходится связывать заново, например:

Существует алгоритм намного проще! Допустим, Алеша вырезал прямоугольник.

Назовем внешними углами прямоугольника шаблоны вида:

Поскольку фигуры не соприкасаются между собой, в том числе по диагонали, то существует всего 4 вида внешних углов. Кроме того, у каждого прямоугольника ровно четыре внешних угла. Если бы Алеша вырезал только прямоугольники, то достаточно было бы посчитать количество внешних углов, а затем разделить их количество на четыре.

Что меняется, когда Алеша вырезает не только прямоугольники?

Рассмотрим следующую фигуру:

У фигуры появился один внутренний угол:

Очевидно, что внутренние углы – инвертированные шаблоны внешних углов. Количество внешних углов увеличилось на 1 – исчезает один старый внешний угол и появляются два новых.

Если же Алеша сделал внутренний вырез из прямоугольника:

То у фигуры появляются два внутренних угла, но появляются и два новых внешних угла! Легко заметить, что какие бы вырезы не делал Алеша, разность между количеством внешних углов и количеством внутренних углов остается постоянной. Это – инвариант. Поэтому число фигур:

F=(Out-In)/4

где Out – количество внешних углов всех фигур, In – количество внутренних углов всех фигур.

Реализовать этот способ в программе очень несложно. В каждый момент времени необходимо хранить только две строки таблицы и сравнивать с шаблоном квадраты размера 2x2.