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

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

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

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

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.

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

Таким образом, при дальнейшем проходе по первой строке, если номер столбца 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, так как новая полоса простирается дальше прежней.

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

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

if maxj < j+d-1 then

maxj := j+d-1;

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

 

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

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

Обратите внимание, что когда мы дойдем до пятой полосы, то указатель 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.

 

 

 

 

Дано клетчатое поле и вырезанные на нем полосы (вертикальные или горизонтальные). Необходимо подсчитать, сколько фигур вырезано.