Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 28.12.2018
Сообщений: 11
1

Задача на динамическое программирование

11.08.2019, 21:57. Показов 939. Ответов 1
Метки нет (Все метки)

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

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

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

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

Примеры
входные данные
3 5
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
выходные данные
3
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.08.2019, 21:57
Ответы с готовыми решениями:

Задача на динамическое программирование
Требуется решить задачу на динамическое программирование. Условия:На планете Олимпия очень...

Задача на динамическое программирование.
Что не правильно? #include <fstream> #include <iostream> using namespace std; int main()...

Задача о НОП (динамическое программирование)
Здравствуйте!!! Мне нужно решить задачу о нахождении наибольшей общей подстроки. Поискал в...

Задача на динамическое программирование(скорее всего) (сколькими способами в сумме получить N, без подряд идущих одинаковых чисел)
Дано число N<106 и три числа A,B,C<=N нужно вывести сколькими способами в сумме получить N, без...

1
812 / 500 / 210
Регистрация: 19.01.2019
Сообщений: 1,196
12.08.2019, 16:17 2
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
 
class Matrix
{
private:
    std::vector<bool> data;
    size_t rows;
    size_t cols;
    
    size_t pathCnt(size_t i, size_t j) {
        if (!(i < rows && j < cols) || !data[i * cols + j]) {
            return 0;
        }
        if (i + j == rows + cols - 2) {
            return 1;
        }
        return pathCnt(i + 1, j) + pathCnt(i, j + 1);
    }
 
public:
    ~Matrix() = default;
    Matrix(size_t n, size_t m) :
        rows(n),
        cols(m),
        data(n * m)
    {}
 
    void fill() {
        short buff;
        for (int i = 0; i < rows * cols; ++i) {
            std::cin >> buff;
            data[i] = buff;
        }
    }
 
    size_t pathCnt() {
        return pathCnt(0, 0);
    }
};
 
 
int main()
{
    size_t N, M;
    std::cin >> N >> M;
    Matrix mx(N, M);
    mx.fill();
 
    size_t cnt = mx.pathCnt();
    if (!cnt) {
        std::cout << "Impossible";
    }
    else {
        std::cout << cnt;
    }
 
    return 0;
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.08.2019, 16:17

Задача "Движение по клеткам таблицы" (Динамическое программирование)
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать...

Динамическое программирование, задача "Уменьшение числа"
Имеется натуральное число N (1 &lt;= N &lt;= 106). За один ход с ним можно произвести следующие действия:...

Динамическое программирование!
#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; int a, n, m; int main() {...

Динамическое программирование
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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