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

@Юлия17071992 · Регистрация: 29.05.2011

Студворк — интернет-сервис помощи студентам

Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.
Формат входных данных
Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).
Формат выходных данных
Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.
Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.
Пример
Входные данные
3 5
11111
10101
11111
Выходные данные
3
Входные данные
3 5
11101
10101
10111
Выходные данные
impossible
Помогите решить, пожалуйста, сдавать через два часа...хоть начало...

valeriikozlov · 28.08.2012, 13:27

Сообщение от -=ЮрА=-

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

Зачем такие сложности? Методом ДП считаются только верные пути, за один проход по массиву.

@-=ЮрА=- · 28.08.2012, 14:02

Сообщение от valeriikozlov

Зачем такие сложности? Методом ДП считаются только верные пути, за один проход по массиву.

valeriikozlov, хорошо перефразирую вопрос - сколько путей выводит ваш алгоритм для приведенного в задании лабиринта?И сколько по настоящему путей существует ?

@-=ЮрА=- · 28.08.2012, 14:05

PS:Это уже для ТС

Сообщение от Юлия17071992

Входные данные
3 5
11111
10101
11111
Выходные данные
3

- не 3 а четыри!

@-=ЮрА=- · 28.08.2012, 14:09

Сообщение от Юлия17071992

3 5
11101
10101
10111
Выходные данные
impossible

- ОМГ, см скриншот
Юля, где в комнате вход где выход?Это ведь концептуально важно описать точку входа и точку выхода, как вообще без этого можно решать указанную задачу

@-=ЮрА=- · 28.08.2012, 14:12

Не по теме:

Юлия17071992, ещё раз призову к посту 5 - для данной задачи более всего подходит поиск в глубину, просто нужно не останавливать DFS как у меня при нахождении первого же пути к выходу, а прогнать алгоритм по всем вершинам и подсчитать число путей обеспечивающих выход...

valeriikozlov · 28.08.2012, 15:42

Сообщение от -=ЮрА=-

valeriikozlov, хорошо перефразирую вопрос - сколько путей выводит ваш алгоритм для приведенного в задании лабиринта?И сколько по настоящему путей существует ?

Сообщение от -=ЮрА=-

- не 3 а четыри!

нет, правильный ответ 3. Четвертый путь не удовлетворяет условию задачи:

Сообщение от Юлия17071992

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

Добавлено через 3 минуты
-=ЮрА=-, Кстати, Вы не правильно путь на тестовом поле изображаете:

Сообщение от Юлия17071992

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

@Юлия17071992 · 30.08.2012, 16:04 **[ТС]**

-=ЮрА=-, сможете ли вы мне полностью прислать код от программки, от которой вы делали скриншоты? а то с помощью этих файлов не могу понять как работает

@pitonist_04ka · 07.04.2020, 11:33

сложность - квадрат, почему TL???!!?!

Python
1
2
3
4
5
6
7
8
9
10
11
n, m = map (int, input ( ).split ( ))
ans1 = [[0] * m for i in range (n)]
for i in range (n):
    k = input().split()
    for j in range(m):
        if i == 0 or j == 0:
            ans1[i][j] = 1
        else:
            ans1[i][j] = int(k[j]) * (ans1[i - 1][j] + ans1[i][j - 1])
 
print (ans1[n - 1][m - 1])

Добавлено через 10 минут
лол, я исправил, но все равно не проходит

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, m = map (int, input ( ).split ( ))
ans1 = [[0] * m for i in range (n)]
for i in range (n):
    k = input().split()
    for j in range(m):
        if i == 0 or j == 0:
            ans1[i][j] = 1
        else:
            ans1[i][j] = int(k[j]) * (ans1[i - 1][j] + ans1[i][j - 1])
 
lol = ans1[n - 1][m - 1]
if lol == 0:
    print('Impossible')
else:
    print(lol)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@Юлия17071992 0 / 0 / 0 Регистрация: 29.05.2011 Сообщений: 55

	найти количество различных маршрутов, ведущих к спасению 17.05.2012, 11:21. Показов 23268. Ответов 27 Метки нет (Все метки) Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению. Формат входных данных Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1). Формат выходных данных Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует. Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000. Пример Входные данные 3 5 11111 10101 11111 Выходные данные 3 Входные данные 3 5 11101 10101 10111 Выходные данные impossible Помогите решить, пожалуйста, сдавать через два часа...хоть начало... 0

@-=ЮрА=-
	28.08.2012, 14:12
	Не по теме: Юлия17071992, ещё раз призову к посту 5 - для данной задачи более всего подходит поиск в глубину, просто нужно не останавливать DFS как у меня при нахождении первого же пути к выходу, а прогнать алгоритм по всем вершинам и подсчитать число путей обеспечивающих выход... 0

@Юлия17071992 0 / 0 / 0 Регистрация: 29.05.2011 Сообщений: 55
	30.08.2012, 16:04 [ТС]
	-=ЮрА=-, сможете ли вы мне полностью прислать код от программки, от которой вы делали скриншоты? а то с помощью этих файлов не могу понять как работает 0