Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
#1

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

17.05.2012, 11:21. Просмотров 681. Ответов 6
Метки нет (Все метки)

Узник пытается бежать из замка, который состоит из 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
Помогите решить, пожалуйста, сдавать через два часа...хоть начало...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2012, 11:21     найти количество различных маршрутов, ведущих к спасению
Посмотрите здесь:

Найти количество различных элементов в массиве. C++
Найти количество различных чисел C++
C++ Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату
Вывести кол-во маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует C++
C++ Количество маршрутов с препятствиями
C++ Найти количество различных элементов в массиве
C++ Определить количество ведущих нулей старшего байта short int
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
17.05.2012, 11:22     найти количество различных маршрутов, ведущих к спасению #2
решить всё за вас? наверное с олимпиады пишете
Юлия17071992
0 / 0 / 0
Регистрация: 29.05.2011
Сообщений: 55
17.05.2012, 12:09  [ТС]     найти количество различных маршрутов, ведущих к спасению #3
Я же не 5 задач написала вам решить, а хотя бы какие-нибудь мысли

Добавлено через 23 минуты
как думаете начать?
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2012, 12:11     найти количество различных маршрутов, ведущих к спасению #4
Динамикой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    
    std::vector< std::vector< int > > matrix(n, std::vector< int > (m) );
    matrix[0][0] = 1;
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            int x;
            std::cin >> x;
            if ( x != 0 )
            {
                if ( i != 0 )
                    matrix[i][j] += matrix[i - 1][j];
                    
                if ( j != 0 )
                    matrix[i][j] += matrix[i][j - 1];
            }
        }
    }
    
    int count = matrix[n - 1][m - 1];   
    if ( count == 0 )
        std::cout << "Impossible";
    else
        std::cout << count;
}
Ternsip
18.05.2012, 12:21
  #5

Не по теме:

diagon, Времени у вас навалом наверное... щедрый вы человек ,или из-за того что Юля17 девушка ?

diagon
18.05.2012, 12:23
  #6

Не по теме:

Цитата Сообщение от Ternsip Посмотреть сообщение
diagon, Времени у вас навалом наверное... щедрый вы человек
У меня минуты две на написание ушло, а подобные задачи я уже решал, так что алгоритм придумывать не пришлось.

Цитата Сообщение от Ternsip Посмотреть сообщение
девушки
Ну это еще не факт, что девушка.

Ternsip
18.05.2012, 12:31     найти количество различных маршрутов, ведущих к спасению
  #7

Не по теме:

diagon, Самое страшно разгрести буквы в условии

Yandex
Объявления
18.05.2012, 12:31     найти количество различных маршрутов, ведущих к спасению
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru