Материал: ЛР4

Варианты

Индивидуальное задание

Узник пытается бежать из замка, который состоит из MN

квадратных комнат, расположенных в виде прямоугольника

M×N. Между любыми двумя соседними комнатами есть дверь,

однако некоторые комнаты закрыты и попасть в них нельзя. В

начале узник находится в угловой комнате и для спасения ему

надо попасть в противоположную угловую комнату. Времени у

него немного, всего он может побывать не более, чем в M+N-1

комнате, включая начальную и конечную комнату на своем

пути, то есть с каждым переходом в соседнюю комнату

расстояние до выхода из замка должно уменьшаться. От вас

требуется найти количество различных маршрутов, ведущих к

1

спасению.

Первая строчка входных данных содержит натуральные числа

M и N, не превосходящих 1000. Далее идет план замка в виде M

строчек из N символов в каждой. Один символ соответствует

одной комнате: если символ равен 1, то в комнату можно

попасть, если он равен 0, то комната закрыта. Первоначальное

положение узника – левый нижний угол (первый символ

последней строки), выход находится в правом верхнем углу

(последний символ первой строки, оба этих символа равны 1).

Программа должна напечатать количество маршрутов, ведущих

узника к выходу и проходящих через M+N-1 комнату, или

слово «Невозможно», если таких маршрутов не существует.

Всем хорошо известна "Игра в 15", представляющая собой 15

2

квадратных фишек, пронумерованных числами от 1 до 15.

Фишки уложены в квадрат со стороной в 4 стороны фишки,

Варианты

Индивидуальное задание

одна позиция для фишки свободна. Если обозначить свободную

позицию за *, то головоломка состоит в том, чтобы получить из

произвольной начальной позиции позицию следующего вида:

1

2

3

4

5

6

7

8

9 10 11 12

13 14 15

*

Единственной разрешенной операцией является обмен * с

одной из соседних по ребру фишек. Операции будем

кодировать буквами:

R – поменять * с фишкой, которая стоит справа от *

L – поменять * с фишкой, которая стоит слева от *

U – поменять * с фишкой, которая стоит сверху от *

D – поменять * с фишкой, которая стоит снизу от *

Например, решением головоломки

1

2

3

4

5

6

7

8

9 10 12 *

13 14 11 15

является последовательность LDR.

От вас требуется решить более простую головоломку "Игра в

8", в которой требуется расположить 8 фишек в виде:

1

2

3

4

5

6

7

8

*

На вход программе подается описание исходной позиции в виде

строки, в которой перечислены номера фишек, разделенные

Варианты

Индивидуальное задание

пробелами в квадрате слева направо сверху вниз. Вместо

свободной фишки напечатана *.

Например, позиция

1

2

3

*

4

6

7

5

8

задается строкой

1 2 3 * 4 6 7 5 8

На выход программа должна вывести одну строку, состоящцю

из букв l, r, u, d, содержащую последовательность операций,

разрешающую данную головоломку, в которой одна буква

соответствует перемещению одной фишки (см. выше правило

кодирования операций). Если же головоломка неразрешима, то

требуется вывести одно слово unsolvable.

На прямоугольном поле для игры в морской бой размером M×N

расположено несколько прямоугольных кораблей. Корабли не

соприкасаются друг с другом. Ваша задача — определить

всевозможные типы кораблей на поле и число кораблей

каждого типа. Два корабля относятся к одному типу, если их

размеры совпадают (корабли, которые могут быть получены

3

друг из друга поворотом, также относятся к одному типу).

Первая строка входных данных содержит два положительных

числа M и N, не превосходящих 1000, задающие размеры поля.

Далее идет M строк, каждая из которых состоит из N символов.

Символ `1' означает, что соответствующая клетка поля занята

кораблем, символ `0' — что свободна. Пробелов в строке нет.

Программа должна для каждого обнаруженного типа корабля

вывести одну строку, содержащую три числа. Первые два числа

Варианты

Индивидуальное задание

Варианты

Индивидуальное задание