Напечатать количество маршрутов, ведущих узника к выходу

напишите/объясните пожалуйста хотя бы алгоритм, как сделать на все случаи. не могу написать полноценную рабочую программу.

задача:
Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.

Формат входных данных

Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).

Формат выходных данных

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

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

0

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

0

Пусть s[a,b] - количество способов попасть в комнату с координатами (a,b).

Тогда:
s[1,1]=1
s[a,b]=s[a-1,b]+s[b,a-1], если комната не закрыта
s[a,b]=0, если комната закрыта.

Я думаю понятно:
1) в начальную комнату только один способ попасть - мы и так уже там;
2) в закрытую комнату мы попасть не можем, а значит есть 0 способов туда попасть;
3) все маршруты до комнаты (a,b) проходят либо через (a-1,b), либо через (a,b-1).

Определяем в цикле s[a,b] для случая a+b=2 (т.е. a=b=1); потом для случая a+b=3; a+b=4, и т.д. Когда доберемся до s[m,n] получим ответ.

Ещё как-то края замка надо будет учесть. Это сами продумайте, тут красивого единственно правильного решения я не вижу.

P.S. Если бы не было закрытых комнат, можно было бы сразу воспользоваться треугольником Паскаля и выдать ответ. Наличие закрытых комнат чуть-чуть усложняет расчёт.

Рекомендую, для общего развития, посмотреть, что такое "треугольник Паскаля", пригодится когда-нибудь.

1

Точно, это же на "динамику"!

Тогда, я бы предложил чуть иначе.

Инициализация по 1й строке:
s[1, 1]:=1;
s[1, j]:=1, но j меняется до тех пор, пока комната открыта, после нахождения закрытой - все остальные s[1, j]:=0
Аналогично, инициализация по 1у столбцу.

А дальше, как вы уже сказали, только просматривать можно и по-строчно, не обязательно радиусом - т.к. в формуле участвуют левая и верхняя клетки.

1

ФедосеевПавел, довольно простой алгоритм получился. Я, вот, тоже, про динамическое программирование не вспомнил.

Начал думать, а "не написать ли мне эту программу", нашёл как инициализацию упростить:
s[1,1]:=1
s[0,j]:=0
s[j,0]:=0

А первую строку и первый столбец по общему алгоритму считаем.

1

Можно код, пожалуйста.

0

Misha3007, а для чего вам нужно решение для задачи с сайта mccme (с электронным судьёй)?

0

Это для Сириуса. Правда там нужно на питоне, но я попытаюсь переделать с паскаля

0

Не понимаю, что такое "Сириус", видимо, онлайн курсы по программированию.
А почему вы не хотите попытаться сделать самостоятельно?

В одной из тем вы написали

Сообщение от Misha3007 Я ещё в 7 классе....

Т.е., если займётесь самостоятельно, то сможете создавать программы. Я начал очень много позже - в 10 классе.
Подойдите к родителям и расскажите, как вам удалось "решить" значительную часть задач с ДОБРОВОЛЬНЫХ курсов. Сомневаюсь, что они одобрят... И делайте из этого выводы.

Попробуйте решить. Задача не сложная. Имеет как минимум два подхода к решению - ввод и последующая обработка матрицы, ввод и одновременная (в потоке) обработка одномерного массива.
Как обрабатывать и подсказка по упрощению инициализации приведены здесь в теме.

Я сейчас перечитал эту тему и сдал именно эту задачу на другом сайте - mccme. Т.е. обсуждения здесь более, чем достаточно.

0

ФедосеевПавел, простите, но все же спрошу. Я всё не могу понять, как я понял программу следует реализовывать через перебор координат, или как то по другому? (решение не нужно, нужно лишь чуть-чуть помочь)

0

mathic, ощущение, что вам лень на листочке нарисовать квадрат 2х2 и для него посчитать пути, потом то же самое для квадрата 3х3.
После этого придёт понимание способа решения.

Идея решения - в том, что у клетки две соседние, из которых можно прийти в неё. Значит количество путей для клетки будет равно сумме путей для соседки сверху и соседки слева.
Это приводит к необходимости знать количество путей для верхнего ряда и клеточек слева.
Таким образом, требуется вычислять пути для ВСЕХ клеточек слева направо сверху вниз.

Добавлено через 4 часа 53 минуты

0

ФедосеевПавел, я пытался

Добавлено через 8 минут
ФедосеевПавел, спасибо, теперь стало понятнее

0

Сейчас дочитался

Сообщение от stirvet Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).

А я решал для левого верхнего, как в задании 2964 mccme.

mathic, в общем, вы теперь разобрались. Поэтому ограничусь тем, что сообщу о своей невнимательности. А ваше решение будет несколько иным - полный ввод матрицы и просмотр с левого нижнего угла по направлению вправо и вверх.

0