Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
180 / 178 / 56
Регистрация: 10.06.2011
Сообщений: 871
1

Количество путей из одной точки в другую

25.10.2015, 19:34. Показов 1771. Ответов 4
Метки нет (Все метки)

Доброго времени суток.

Есть такая задачка: дана матрица, состоящая из нулей и единиц. Требуется посчитать количество путей из нижнего левого угла, в верхний правый, при этом чтобы кол-во шагов не превышало 8 и двигаться мы можем только по единицам (рядом стоящим).

Думается мне что задачка или графовая или рекуррентная, но с решением туговато.

Может кто что подскажет (темку из теории графов или алгоритм)?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.10.2015, 19:34
Ответы с готовыми решениями:

Доступ из одной сети в другую от точки А до точки Б без шлюза в точке Б
Здравствуйте уважаемые профессионалы! В сетях не силен поэтому спрашиваю, сильно не ругайте)...

Движения с одной точки в другую
Нужна сделать движения между двомя пустими обєктами. Как реализиривать? Типа Т.Д.

Движение шарика с одной точки в другую
Надо сделать движение шарика с одной точки в другую.

Попасть из одной точки двумерного массива в другую
Создать вектор, в котором генерируются вектора разной длинны (аналог ступенчатого массива), и...

4
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,516
Записей в блоге: 22
25.10.2015, 20:30 2
Лучший ответ Сообщение было отмечено Ryuk как решение

Решение

Ну начнем с того, что если сумма количества строк и столбцов матрицы больше 10, то за 8 шагов не доберемся. Если меньше - то рекурсия, поиск в глубину до максимум 8 шагов.
1
Dimension
583 / 451 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
25.10.2015, 21:15 3
динамикой ,только у меня с левого верхнего в правый нижний
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
#include <bits/stdc++.h>
using namespace std;
const int n=5;
const int INF = 1e9;
int dp[n+2][n+2],a[n+1][n+1];
 
int main(){
    for (int i = 0;i < n + 2;i++)
        for (int j = 0;j < n + 2;j++)
            dp[i][j] = INF;
    for (int i = 1;i < n + 1;i++)
        for (int j = 1;j < n + 1;j++) 
            cin >> a[i][j];
            
    
    dp[1][1] = a[1][1];
    for (int i = 1;i < n + 1;i++) {
        for (int j = 1;j < n + 1;j++) {
            if (a[i][j] && i!=1) {
                int t = min(min(dp[i][j + 1], dp[i][j - 1]), min(dp[i + 1][j], dp[i - 1][j])) + 1;
                dp[i][j] = t;
            }
        }
    }
    cout << dp[n][n];
    return 0;
}
1
180 / 178 / 56
Регистрация: 10.06.2011
Сообщений: 871
25.10.2015, 21:25  [ТС] 4
Dimension, спасибо конечно, но меня интересовало не решение, а алгоритм.
С решением я как нибудь уж сам.
0
Dimension
583 / 451 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
25.10.2015, 21:26 5
тогда ищите в интернете двумерное динамическое программирование
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.10.2015, 21:26

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Перемещение объекта из одной точки в другую и обратно
сделал цикл: for (int i = 1; i == 1; i++) { if...

Как провести линию из одной точки формы в другую?
Хотелось бы узнать как средствами Delphi провести линию из одной точки формы в другую.(аналог line...

Трансляция точки из одной проекции в другую 3-мерного обьекта в пространстве
Есть такая задача : есть трехмерный обьект в пространстве. Есть несколько фотографии етого обьекта,...

Найти кротчайший путь передвижения коня из одной точки в другую
Нужно писать курсовую, кто может помочь, перелопатил весь интернет, ничего не нашел с обьяснениям,...


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

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

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