arrays4 - Программирование на языке C++

��: struct, ��: arrays3, ��: Top

12 Маршруты на плоскости

Никакой теории, только задачи. Некоторые из задач данного листка взяты из курса В.А.Матюхина: www.olympiads.ru/problems/8v-03/

Треугольник Паскаля. Дано число n. Выведите первые n строк треугольника Паскаля. Числа при выводе разделяйте одним пробелом. Ниже приведен пример для n=6.
```
          1
          1 1
          1 2 1
          1 3 3 1
          1 4 6 4 1
          1 5 10 10 5 1
```
Хождение за золотом -1. Однажды царь решил вознаградить одного из своих мудрецов за хорошую работу. Он привел его в прямоугольную комнату размером NxM, в каждой клетке которой лежало несколько килограммов золота. Царь разрешил мудрецу сделать обойти несколько клеток (переходя с клетки, где сейчас находится мудрец, в одну из четырех с ней соседних), и собрать все золото, которое попадется на его пути.
Вам дан маршрут мудреца. Требуется определить, сколько килограммов золота он собрал. Если мудрец проходит через одну клетку более одного раза, то он собирает с нее золото только в первый проход.
Входные данные. Входные данные состоят из двух частей: плана комнаты и маршрута мудреца. Сначала записано количество строк в плане команаты N, затем - количество столбцов M. Затем записано N строк по M целых чисел в каждой – количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число K – сколько клеток обошел мудрец. Затем идет K строк с координатами этих клеток (координаты клетки – это два числа: первое определяет номер строки, второе – номер столбца, верхняя левая клетка на плане имеет координаты (0, 0), правая нижняя - (N-1,M-1)).
Выведите количество килограммов золота, которое собрал мудрец.
Пример
```
          Вход                       Выход
          3 4                         14
          1 2 3 4
          5 6 7 8
          9 0 0 0
          5
          0 0
          0 1
          1 1
          1 0
          0 0
```
Хождение за золотом - 2. Задача, аналогичная предыдущей, только маршрут мудреца задан по-другому: в виде последовательности перемещения (налево, направо, вверх, вниз).
Входные данные. Сначала задается план комнаты, как в предыдущей задаче. Далее указано количество клеток K, которое обошел мудрец. Мудрец начинает свое перемещение из клетки (0, 0) – левого верхнего угла комнаты. Далее идет последовательность из K-1 буквы, разделенных пробелами, задающими направление перемещения мудреца на каждом шаге. Возможные направления: L – влево, R – вправо, U – вверх, D – вниз. Программа должна вывести количество килограммов золота, которое собрал мудрец или слово Error, если заданная последовательность некорректна (мудрец натыкается на стенку комнаты).
Пример
```
          Вход              Выход
          3 3               45
          1 2 3
          4 5 6
          7 8 9
          9
          D D R R U U L D
          
          Вход              Выход
          2 2               Error
          1 1
          1 1
          4
          R D R
```
Попытка к бегству - 1. В левом верхнем углу прямоугольной таблицы размером NxM клеток стоит фишка. Ее можно передвигать либо вправо, либо вниз, пока она не достигнет правого нижнего угла. Определите количество различных маршрутов, которые ведут из левого верхнего в правый нижний угол.
На вход программа получает два числа N и M, не превосходящие 10. Программа должна вывести количество искомых маршрутов
Пример
```
          Вход                    Выход
          2 3                      3
```
Попытка к бегству - 2. Узник пытается бежать из замка, который состоит из NM квадратных комнат, расположенных в виде прямоугольника NxM. Между любыми двумя соседними комнатами есть дверь, однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в левой верхней комнате и для спасения ему надо попасть в противоположную правую нижнюю комнату. Времени у него немного, всего он может побывать не более, чем в N+M-1 комнате на своем пути, то есть перемещаться он должен только вправо или вниз. Определите количество маршрутов, которые ведут к выходу.
Входные данные. Первая строчка входных данных содержит натуральные числа N и M, не превосходящих 1000. Далее идет план замка в виде N строчек из M чисел в каждой. Одно число соответствует одной комнате: 1 означает, что в комнату можно попасть, 0 – что комната закрыта. Формат выходных данных
Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово Impossible, если таких маршрутов не существует.
Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.
Пример
```
          Вход                Выход
          3 5                  3
          1 1 1 1 1
          1 0 1 0 1
          1 1 1 1 1
          
          Вход                Выход
          3 5                  Impossible
          1 0 1 1 1
          1 0 1 0 1
          1 1 1 0 1
```
Хождение за золотом - 3. Как всегда, мудрец собирает золото в комнате размером NxM. Он начинает из левого верхнего угла, может сделать ровно N-1 переход вниз и ровно M-1 переход вправо в произвольном порядке и закончить путь в правом нижнем углу комнаты. Программа получает на вход план комнаты и выводит максимальное число золота, которое сможет собрать мудрец.
Пример
```
          Вход                  Выход
          3 4                   9
          1 1 2 1
          2 2 1 1
          2 1 2 1
```
В данном примере число 9 можно достигнуть, например, при помощи следующей последовательности перемещений: D R D R R.
Хождение за золотом - 4. Условие задачи аналогично предыдущей, только программа должна кроме искомого количества золота вывести еще и маршрут, которому должен следовать мудрец, чтобы собрать это количество. Первая строка выходных данных содержит собранное количество золота, вторая – необходимый для этого маршрут. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
Пример
```
          Вход                  Выход
          3 4                   9
          1 1 2 1               D R D R R
          2 2 1 1
          2 1 2 1
```

Вход в тестирующую систему

Текущие результаты.