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

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

Войти
Регистрация
Восстановить пароль
 
 
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
#1

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

03.11.2011, 21:37. Просмотров 1024. Ответов 16
Метки нет (Все метки)

кому не трудно помогите сделать. если не трудно вам написать код.

Дана прямоугольная таблица 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
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2011, 21:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку. (C++):

Минимальный путь из левой верхней в правую нижнюю клетку таблицы. - C++
Не могу понять в чем ошибка...помогите. Химическая тревога (Время: 1 сек. Память: 16 Мб Сложность: 50%) Произошло радиоактивное...

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N - C++
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы...

Может ли пешка выполнить ход из клетки с координатами (X1, Y1) в клетку с координатами (X2, Y2)? - C++
Здрасти, я вам тут задачку принес. Напомним, что в шахматах используется клеточная доска размером 8х8, где располагаются шахматные...

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

Есть пирог. Игроки по очереди выбирают какую-либо клетку пирога. Определить проигравшего - C++
Пирог.Имеетсяпрямоугольныйпирог,разрезанныйнаm×nчастей (клеток),причем,леваянижняяклеткапирогаотравлена.Игроки по...

Создать запись в клетку ссылки на другую клетку, запись в клетку функции суммирования блока клеток - C++ Builder
Ребят, подскажите- только начала изучать программу, создала таблицу, не получается создать запись в клетку ссылки на другую клетку, запись...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Bers
Заблокирован
03.11.2011, 21:48 #2
Montanaa, толи я задачу не понял, толи у меня получилось, что цена пути из примера - 1, а не 5
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
03.11.2011, 21:49 #3
Все там верно, 5.
0, 0 -> 0, 1 -> 0, 2 -> 1, 2 -> 2, 2 -> 2, 3 -> 2, 4
0
Bers
Заблокирован
03.11.2011, 21:51 #4
neske, аааа... туплю)
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 21:52 #5
динамика..
0
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 21:56  [ТС] #6
да, динамика)
0
Ланселот
6 / 6 / 1
Регистрация: 30.08.2011
Сообщений: 32
03.11.2011, 21:57 #7
У обоих правильный ответ, так как двигаться можно по-разному. Движение вниз не является главным. Тема, ИМХО не для начинающих. Тут еще и бэккинг придется задействовать, если, скажем, на последней строчке, двигаясь вправо, упремся в "х".
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.11.2011, 22:00 #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] - можно прийти слева и сверху, из двух вариантов выбирается максимальный.
Ну и препятствия учесть.
Ланселот, для начинающих. Это очень простая динамика.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 22:07 #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
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.11.2011, 22:15 #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];     
}
3
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 22:24 #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' );
0
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 22:44  [ТС] #12
а как убедится, что маршрута не существует?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 22:59 #13
diagon, очень сильно извиняюсь перед Вами, но Ваш код правильный полностью (это я его не совсем рассмотрел - есть причины).
Montanaa, в коде diagon вычисляется все полнстью и в том числе, если маршрута не существует.
1
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 23:05  [ТС] #14
Вывожу SEE YOU LATER если маршрута не существует. почему то не правильно работает
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.11.2011, 23:06 #15
Montanaa, показывайте весь код.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2011, 23:06
Привет! Вот еще темы с ответами:

Найти такой путь из клетки (1,1) в клетку (А, В), чтобы сумма чисел равнялась заданному числу К - Pascal ABC
Помогите написать программу к задаче Дано шахматную доску размером М на N. Шахматная фигура &quot;мини-тура&quot; может перемещаться только на...

Определить, можно ли с клетки (k, l) одним ходом ферзя попасть на клетку (m, n) - Turbo Pascal
Поле для шахмат определяется парой натуральных чисел, каждое из которых не превышает восьми: первое число - номер по вертикали( при счета...

Собирание всех коней в одну клетку доски или количество коней, которые немогут прийти в даную клетку - Pascal
Может кто-то помочь срочно решить олимпиадную задачку. На шахматной доске размером NxM (2 ≤ N, M ≤ 100) находится Q (0 ≤ Q ≤ 10000)...

Игра. Игроки по очереди вычеркивают 1 или 2 или 3 клетки, следующие подряд. Проигрывает тот, кто вычеркнет последнюю клетку - Pascal ABC
Всем привет!! Есть полоска из 11 клеток. Играют 2 игрока, по очереди вычеркивают 1 или 2 или 3 клетки, следующие подряд. Проигрывает тот,...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.11.2011, 23:06
Ответ Создать тему
Опции темы

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