На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».

Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.

Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.

«Что за свинья прошла здесь - корова, что ли?»

Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.

К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.

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

Напишите программу, вычисляющую это минимальное число разрезов.

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

Замечание для тех, кто не умеет играть в шахматы:

Шахматная доска имеет размеры 8*8. Ладья бьет все клетки горизонтали и вертикали, проходящих через клетку, где она стоит, до первой встретившейся фигуры. Офицер бьет все клетки обеих диагоналей, проходящих через клетку, где он стоит, до первой встретившейся фигуры.

Правительство страны Ректилании решило построить новый город. По плану правительства, город должен быть построен на сетке M на N прямоугольных участков, размером 100 на 100 метров. Все улицы должны иметь ширину 100 метров и занимать соответственно одну горизонталь или вертикаль сетки. Вертикальные улицы должны пролегать по вертикалям с номерами X₁...X_V, горизонтальные – по горизонталям с номерами Y₁...Y_H. При этом улицы не соприкасаются, то есть не бывает X_i = X_i-1 + 1 и соответственно Y_j = Y_j-1 + 1 .

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

Теперь правительство Ректилании хочет знать, сколько домов будет построено в новом городе и сколько в нем будет клеток парка. Ваша задача состоит в том, чтобы написать программу, которая рассчитает эти величины.

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной w и высотой h, разбитых на w×h единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «исключающее ИЛИ» эта таблица выглядит так.

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