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

Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. - C++

Восстановить пароль Регистрация
 
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 21:37     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #1
кому не трудно помогите сделать. если не трудно вам написать код.

Дана прямоугольная таблица nxn клеток. В каждой клетке содержится либо цифра (от 0 до 9), либо символ "x" (препятствие). Стоимостью пути называется сумма цифр на посещенных клетках. Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на соседнюю правую или нижнюю клетку.

Входные данные
В первой строке записаны два числа n и m (1<=n<=80, 1<=m<=80, n + m > 2) - количества строк и столбцов таблицы соответственно. Далее в n строках записано по m символов, описывающих таблицу. Гарантируется, что клетки (1, 1) и (n, m) не содержат "x".

Выходные данные
Выведите искомую стоимость или фразу "see you later", если искомого пути не существует.

Пример

Ввод
3 5
0044x
300x7
00100

Вывод
5
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2011, 21:37     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
Посмотрите здесь:

Может ли в Ц переменная иметь переменные значения? Строки... C++
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N C++
C++ Шаг компиляции, шаг компоновки, и шаг запуска
C++ Заполнить квадрат углами и оставить одну пустую клетку
C++ Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Bers
Заблокирован
03.11.2011, 21:48     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #2
Montanaa, толи я задачу не понял, толи у меня получилось, что цена пути из примера - 1, а не 5
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,692
03.11.2011, 21:49     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #3
Все там верно, 5.
0, 0 -> 0, 1 -> 0, 2 -> 1, 2 -> 2, 2 -> 2, 3 -> 2, 4
Bers
Заблокирован
03.11.2011, 21:51     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #4
neske, аааа... туплю)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 21:52     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #5
динамика..
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 21:56  [ТС]     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #6
да, динамика)
Ланселот
6 / 6 / 1
Регистрация: 30.08.2011
Сообщений: 32
03.11.2011, 21:57     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #7
У обоих правильный ответ, так как двигаться можно по-разному. Движение вниз не является главным. Тема, ИМХО не для начинающих. Тут еще и бэккинг придется задействовать, если, скажем, на последней строчке, двигаясь вправо, упремся в "х".
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.11.2011, 22:00     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
динамика..
Угу.
Алгоритм примерно такой:
Завести матрицу n * m и заполнять ее.
Пусть d - матрица под динамику, a - исходная матрица со значениями.
d[0][0] = a[0][0] ( попасть сюда можно одним путем - остаться в этой клетке ).
d[0][i] = d[0][i - 1] +a[0][i] - в крайние верхние клетки можно попасть только слева
d[i][0] = d[i - 1][0] + a[i][0] - в крайние левые клетки можно попасть только сверху.
d[i][i] = max( d[i - 1][j], d[i][j - 1] ) + a[i][j] - можно прийти слева и сверху, из двух вариантов выбирается максимальный.
Ну и препятствия учесть.
Ланселот, для начинающих. Это очень простая динамика.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 22:07     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #9
Если по быстрому решать то так:
имеем массив char mas[n][m], заполненный такими значениями:
0044x
300x7
00100
создаем свой массив a[n][m] заполненный значениями -1,
далее так:
C++
1
2
3
4
5
6
7
8
9
10
11
a[0][0]=(int)(mas[0][0]-'0');
for(int i=1; i<m; i++)
   if(mas[0][i]!='x')
        a[0][i]=a[0][i-1]+(int)(mas[0][i]-'0');
   else
        break;
for(int i=1; i<n; i++)
   if(mas[i][0]!='x')
        a[i][0]=a[i-1][0]+(int)(mas[i][0]-'0');
   else
        break;
Дальше так:
C++
1
2
3
4
for(i=1; i<n; i++)
    for(j=1; j<m; j++)
        if((a[i][j-1]!=-1 || a[i-1][j]!=-1) && mas[i][j]!='x')
            a[i][j]=max(a[i][j-1], a[i-1][j])+(int)(mas[i][j]-'0');
Выводим a[n-1][m-1]
Еще не учел вариант когда mas[i][j]=='x' - можно в этом случае отдельно вывести -1
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.11.2011, 22:15     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Не тестировал, но примерно так:
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< char > > matrix(n, std::vector< char > (m) );
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            std::cin >> matrix.at(i).at(j);
    
    std::vector< std::vector< int > > dinamic(n, std::vector< int > (m, -1) );
    dinamic.at(0).at(0) = matrix.at(0).at(0) - '0';
    for ( int i = 0; i < n ; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if ( i == 0 && j == 0 )
                continue;
            
            if ( matrix[i][j] == 'x' )
                continue;
                
            if ( i > 0 && dinamic[i - 1][j] != -1 )
                dinamic[i][j] = dinamic[i - 1][j] + matrix[i][j] - '0';
            if ( j > 0 && dinamic[i][j - 1] != -1 )
                dinamic[i][j] = std::max( dinamic[i][j], dinamic[i][j - 1] + matrix[i][j] - '0' );
        }
        
    }
    
    std::cout << dinamic[n - 1][m - 1];     
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 22:24     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #11
diagon, Тоже не тестировал, но вижу пробелы:

Цитата Сообщение от diagon Посмотреть сообщение
if ( i > 0 && dinamic[i - 1][j] != -1 )
dinamic[i][j] = dinamic[i - 1][j] + matrix[i][j] - '0';
если matrix[i-1][0]=='x' (при j==0), а соответственно dinamic[i - 1][0]==-1, то dinamic[i][0] будет иметь значение отличное от -1
то же самое и для:

Цитата Сообщение от diagon Посмотреть сообщение
if ( j > 0 && dinamic[i][j - 1] != -1 )
dinamic[i][j] = std::max( dinamic[i][j], dinamic[i][j - 1] + matrix[i][j] - '0' );
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 22:44  [ТС]     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #12
а как убедится, что маршрута не существует?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 22:59     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #13
diagon, очень сильно извиняюсь перед Вами, но Ваш код правильный полностью (это я его не совсем рассмотрел - есть причины).
Montanaa, в коде diagon вычисляется все полнстью и в том числе, если маршрута не существует.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 23:05  [ТС]     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #14
Вывожу SEE YOU LATER если маршрута не существует. почему то не правильно работает
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 23:06     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #15
Montanaa, показывайте весь код.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 23:10  [ТС]     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #16
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Montanaa, показывайте весь код.
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
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
        int n, m;
        cin >> n >> m;
 
    vector<vector<char>> arr(n, vector<char> (m));
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
     
    vector<vector<int>> z(n, vector<int> (m, - 1));
        z[0][0] = arr[0][0] - '0';
        for (int i = 0; i < n ; ++i)
        {
        for (int j = 0; j < m; ++j)
        {
            if (i == 0 && j == 0)
                continue;
                
                if (arr[i][j] == '*')
                    continue;
                
                if (i > 0 && z[i - 1][j] != -1)
                    z[i][j] = z[i - 1][j] + arr[i][j] - '0';
 
                if (j > 0 && z[i][j - 1] != -1)
                    z[i][j] = max(z[i][j], z[i][j - 1] + arr[i][j] - '0');
            }
        }
        
        if (z[n - 1][m - 1])
            cout << z[n - 1][m - 1] << endl;
        else
            cout << "SEE YOU LATER" << endl;
 
        return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2011, 23:15     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
Еще ссылки по теме:

Можно потоком читать файл, если он может с любым переводом строки? C++
Есть пирог. Игроки по очереди выбирают какую-либо клетку пирога. Определить проигравшего C++
Поменять местами левую верхнюю и правую нижнюю четверти матрицы - С и C++ C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 23:15     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. #17
Цитата Сообщение от Montanaa Посмотреть сообщение
if (z[n - 1][m - 1])
cout << z[n - 1][m - 1] << endl;
else
cout << "SEE YOU LATER" << endl;
заменить на:
C++
1
2
3
4
if (z[n - 1][m - 1]!=-1)
 cout << z[n - 1][m - 1] << endl;
 else
 cout << "SEE YOU LATER" << endl;
Yandex
Объявления
03.11.2011, 23:15     Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
Ответ Создать тему
Опции темы

Текущее время: 04:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru