Занятие №6. Задачи на анализ таблиц.

Теория: Лекция                            [Все занятия]

Практика:                                 [Официальная страница]

Учебные задачи:
   Задача А.
   [Побочная диагональ]
Хорошая незатейливая задача =) 
   Задача В.
   [Шахматная доска]
Т.к. изначально сказано, что область является связной, то нет необходимости писать поиск в глубину(лишний расход памяти на рекурсию) или поиск в ширину(просто дольше писать). Достаточно перебрать 64 клетки поля и определить периметр, просмотрев все соседние клетки. В этой задаче не лишним будет обнести всё поле границей фиктивными клетками, чтобы не писать дополнительные проверки на выход за пределы шахматной доски.
   Задача С.
   [Поворот]
Если бы требовалось в результате программы получить матрицу, то предложенное решение требует дополнительно O(N*N) памяти. Можно придумать решение, в котором все манипуляции происходят на исходной матрице. Для этого вычленяем 4 угловые клетки и делаем их циклический сдвиг. Последовательно перебираем все возможные такие четверки и получаем ответ. Учитывая небольшие ограничения, данное решение не приводится.
Олимпиадные задачи:
  Задача А.
   [Сапер]
Классика жанра. Опять же очень удачной мыслью будет обнести поле фиктивными клетками, чтобы отдельно не проверять случай выхода за границы поля. 
  Задача В.
   [Игра с фишками]
Очень хорошая задача, чтобы попрактиковаться в реализации BFS на таблицах. В данной задаче я не обносил матрицу фиктивными элементами. Вместо этого использовалась функция correct(int x, int y) для проверки выхода за пределы игрового поля. 
   Задача С.
   [Вырезание фигуры]
Можно хранить всю матрицу целиком, а связные области находить BFS’ом. Но можно поступить более изящно. Можно искать углы фигуры. По условию сказано, что фигуры не пересекаются и не соприкасаются углами или сторонами, следовательно можно выделить двоичные маски углов, а именно:
0|1   1|0   1 1    1 1
1 1   1 1   0|1    1|0   - являются битовыми масками внешних углов(OUT) вырезанной фигуры.

также существуют внутренние углы(IN) фигуры. Битовые маски внутренних углов фигуры получаются инверсией битовых масок внешних углов. Показателен тот факт, что для любой вырезанной фигуры верна формула: OUT – IN = 4.
Дополнительные олимпиадные задачи:
  Задача А.
   [Восстанови многоугольник]
Лучше разбор наверное не придумать: [Автор: Владимир Гуровиц]
   Задача В.
   [Электронные часы]
Казалось бы несложная задача. Но здесь есть пара подводных камней. В частности количество часов может получиться больше 23, а количество минут больше 59. Эти две ситуации нужно корректно обработать. Я это сделал таким образом:
1) 4 списка возможных значений на каждое цифровое поле часов.
2) Получил все возможные комбинации часов перебрав все допустимые пары первой и второй цифры.
3) Получил все возможные комбинации минут перебрав все допустимые пары третьей и четвертой цифры
4) Отсеял все невалидные значения часов и минут.
Если хотя бы один из списков пуст, значит произошла ошибка. Выводим ERROR
Если хотя бы в одном списке больше 1 элемента, значит возможна двоякая интерпретация. Выводим AMBIGUITY.
В противном случае в каждом списке по одному элементу, т.е. удалось однозначно установить время. Выводим его. B здесь нас ждет еще один подводный камень. Нужно не забыть про ведущие нули.
   Задача С.
   [Историки и археологи]
Если присмотреться, то можно заметить, что процедура переселения представляет собой обычное транспонирование подматрицы. В результате чего происходит реверс элементов относительно главной диагонали. Вот собственно и на этом будет строиться наше решение. Для начала условимся, что будем приводить первую матрицу ко второй последовательно, подиагонально. Диагонали будем перебирать слева-направо, сверху-вниз, т.е. первая диагональ будет состоять из одного элемент (0,0), вторая диагональ из двух – (1,0) и (1,0) и т.д. Транспонирование нужно выполнять осторожно. Если в качестве подматрицы выбрать матрицу размером большим, чем 2*2, то произойдут обмены элементов прошедших и уже упорядоченных диагоналей. Поэтому в качестве подматрицы будем использовать только матрицы размером 2*2. А транспонирование подматрицы будет идентично реверсу побочной диагонали, или обмену двух соседних элементов текущей диагонали. При упорядочивании диагонали будем использовать принцип аналогичный сортировки пузырьком.