Написать программу на С++ (задание 2 курса) !обязательно с++!

Написать программу, решающую любую из 3х задач:

1. Имеетсяклеточное поле размера M x N , в некоторых позициях ко- торого расставлены

черные фигуры, M – количество столбцов, а N – ко- личество строк. Расставить

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

Рекомендация: минимальное вершинное покрытие графа, вершинами которого будут

все свободные клетки, и будет существовать ребро (x,y), если при постановке

коня в клетку x будет пробиваться клетка y.

2. Имеется клеточное поле размера M x N , в некоторыхпозициях ко- торого расставлено K черных фигур. Необходимо расставить

максималь- ное число белых коней, чтобы они не били друг друга. Рекомендация:

двудольный граф, соответствующий нашей доске: вершины – клетки не занятые

черными фигурами, ребро между верши- ной А и В устанавливается в том случае,

если конь за один ход может по- пасть из вершины А в вершину B.

3. Имеетсяклеточное поле размера N x M , в некоторых позициях ко- торого расставлены

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

способами фишки таким образом, чтобы в каждой линии (горизонтальной,

вертикальной, диагональной) располага- лось четное число фишек. Рекомендация:

строим дерево перебора. Его вершиной будет комби- нация значений свободных переменных

из множества {0,1}. Корнем бу- дет комбинация всех свободных переменных,

приравненных нулю. На каждом шаге приравниваем текущую переменную нулю (левая

ветка) или единице (правая ветка). Всего вершин в дереве будет 2K . Высота де

рева составит k.